자료구조 & 알고리즘/프로그래머스

[프로그래머스] #.42862 - 체육복

체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 전체 학생의 수는 2명 이상 30명 이하입니다.
  • 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
  • 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
  • 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
  • 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

n lost reserve return
5 [2,4] [1,3,5] 5
5 [2,4] [3] 4
3 [3] [1] 2

문제 해결하기

func solution(n int, lost []int, reserve []int) int 

이 문제는 제한사항을 잘 확인해야 한다. 여별 체육복이 있는 학생이란, reserve 에 있는 것이고, 여벌 체육복을 가져왔으나 도난 당했다는 것reserve 에도 있고 lost 에도 존재한다는 이야기다. 따라서 이러한 경우, 아무런 의미도 없다고 해석할 수 있으므로 계산에서 완전히 제외시켜야 한다. 이를 생각해보면 다음과 같은 코드가 나온다.

// 여벌 체육복을 가져왔으나 도난 당한 경우는 제외한다.
for p := 0; p < len(lost); p++ {
	for q := 0; q < len(reserve); q++ {
		if reserve[q] == lost[p] {
			lost = remove(lost, p)
			p--
			reserve = remove(reserve, q)
			q--
			break
		}
	}
}

여기서 remove() 함수는 슬라이스에서 특정 인덱스의 요소를 제거한다. 따라서 반복문이 돌아가는 와중에 배열의 크기가 줄어든다. 그래서 반복자의 크기를 각각 -1 처리해주는 것을 볼 수 있다.

 

그 다음 처리해주어야 하는 사항은 문제에도 나와 있듯이, 체육복을 잃어버린 사람의 앞과 뒤의 번호의 학생에게만 빌릴 수 있다는 것이다. 체육복을 빌린 번호는 lost 에서 사라질 것이고, 체육복을 빌려준 번호는 reserve 에서 사라질 것이다. 또한 이러한 경우 체육수업을 받을 수 있는 학생이 하나 증가된다고 여길 수 있으므로 can 변수의 값을 하나 증거시켜 준다.

can := n - len(lost) // 체육수업을 들을 수 있는 학생 수

// 체육복을 잃어버린 학생이 앞, 또는 뒤 번호에 체육복을 빌려준다.
for p := 0; p < len(lost); p++ {
	for q := 0; q < len(reserve); q++ {
		if reserve[q] == lost[p]-1 || reserve[q] == lost[p]+1 {
			can++
			lost = remove(lost, p)
			p--
			reserve = remove(reserve, q)
			q--
			break
		}
	}
}

해당 솔루션에 대한 테스트케이스는 다음과 같다.

func TestSolution(t *testing.T) {
	cases := []struct {
		n       int
		lost    []int
		reserve []int
		expect  int
	}{
		{5, []int{2, 4}, []int{1, 3, 5}, 5},
		{5, []int{2, 4}, []int{3}, 4},
		{3, []int{3}, []int{1}, 2},
		{5, []int{2, 4, 5}, []int{4, 1}, 4},
		{5, []int{2, 4}, []int{2, 3, 5}, 5},
		{5, []int{2, 3, 5}, []int{2, 3}, 4},
		{5, []int{1, 2, 4, 5}, []int{2, 3, 4}, 3},
	}
	for _, c := range cases {
		if r := solution(c.n, c.lost, c.reserve); r != c.expect {
			t.Errorf("n: %#v, lost: %#v, reserve: %#v; got %#v, want %#v", c.n, c.lost, c.reserve, r, c.expect)
		}
	}
}

remove(s int, i int) []int

remove() 함수는 내장 함수가 아니므로 직접 구현해야 한다. 마지막/처음 요소를 제거하는 경우와 중간 요소를 제거하는 경우, 이렇게 세가지의 경우가 있다. 배열이라는 자료구조의 특징상 중간에 있는 요소를 제거하기 위해서는 뒤에 있는 요소를 하나씩 당겨야 하지만, Go 에서는 슬라이스로 처리할 수 있다.

func remove(s []int, i int) []int {
	switch {
	case len(s)-1 == i:
		return append(s[:len(s)-1])
	case i == 0:
		return append(s[1:])
	default:
		return append(s[:i], s[i+1:]...)
	}
}

func TestRemove(t *testing.T) {
	cases := []struct {
		s      []int
		i      int
		expect []int
	}{
		{[]int{0, 1, 2}, 0, []int{1, 2}},
		{[]int{0, 1, 2}, 1, []int{0, 2}},
		{[]int{0, 1, 2}, 2, []int{0, 1}},
	}
	for _, c := range cases {
		c.s = remove(c.s, c.i)
		if len(c.s) != len(c.expect) {
			t.Errorf("got %#v, want %#v", c.s, c.expect)
			return
		}
		for i, v := range c.s {
			if v != c.s[i] {
				t.Errorf("#%d, got %#v, want %#v", i, c.s, c.expect)
			}
		}
	}
}

더 읽을거리

https://github.com/pronist/al.go/tree/main/programmers/_42862

https://programmers.co.kr/learn/courses/30/lessons/42862