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

[al.go] #.42840 - 모의고사 [프로그래머스]

모의고사

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

  • 시험은 최대 10,000 문제로 구성되어있습니다.
  • 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
  • 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answers return
[1,2,3,4,5] [1]
[1,3,2,4,2] [1,2,3]

문제 해결하기

이 문제에서 중요하게 봐야하는 것은 각각 번호에 해당하는 수포자가 문제를 찍는 방식에서 보여지는 연속된 패턴이다. 1번 수포자는 1,2,3,4,5, 2번 수포자는 2,1,2,3,2,4,2,5, 3번 수포자는 3,3,1,1,2,2,4,4,5,5 가 반복된다. 따라서 이러한 패턴만 파악하면 풀어낼 수 있다.

type p struct

먼저 각각의 수포자에 대응하는 타입에 대해 정의를 해둘 필요가 있다.

type p struct {
	pattern []int // 각 수포자의 패턴
	i       int // 내부 이터레이터
	count   int // 문제를 맞춘 횟수
}

.resolve(answer int)

해당 메서드에서는 P 타입에 포함되어 있는 내부 이터레이터라는 것을 사용하게 된다. 각 수포자가 가지고 있는 패턴의 길이는 문제에서 보다시피 제 각각이며 문제에 주어지는 answers 에 대해 대응을 해줄 필요가 있다.

 

ipattern 배열에 대한 인덱스다. 반복문을 통해 패턴을 반복하고 나면, 다시 처음으로 되돌아가 패턴을 다시 검증해줄 필요가 있는데, 만약 인덱스가 배열의 마지막 인덱스에 되돌아가면 0 으로 초기화한다. 느낌만 보자면 환형 링크드 리스트와 비슷하다.

func (p *p) resolve(answer int) {
	// 내부 이터레이터가 패턴의 마지막에 도달한 경우 리셋해야 한다.
	if p.i >= len(p.pattern) {
		p.i = 0
	}
	// 패턴과 문제의 답이 일치하는 경우 Count 를 증가시킨다.
	if answer == p.pattern[p.i] {
		p.count++
	}
	p.i++
}

func TestP_Resolve(t *testing.T) {
	cases := []struct {
		p       p
		answers []int
		expect  int
	}{
		{p{[]int{1, 2, 3, 4, 5}, 0, 0}, []int{1, 2, 3, 4, 5}, 5},
		{p{[]int{2, 1, 2, 3, 2, 4, 2, 5}, 0, 0}, []int{1, 2, 3, 4, 5}, 0},
		{p{[]int{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}, 0, 0}, []int{1, 2, 3, 4, 5}, 0},
		{p{[]int{1, 2, 3, 4, 5}, 0, 0}, []int{1, 3, 2, 4, 2}, 2},
		{p{[]int{2, 1, 2, 3, 2, 4, 2, 5}, 0, 0}, []int{1, 3, 2, 4, 2}, 2},
		{p{[]int{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}, 0, 0}, []int{1, 3, 2, 4, 2}, 2},
	}
	for _, c := range cases {
		for _, answer := range c.answers {
			c.p.resolve(answer)
		}
		if c.p.count != c.expect {
			t.Errorf("got %#v, want %#v", c.p.count, c.expect)
		}
	}
}

func biggest(counts []int) []int

해당 함수는 들어온 counts 배열에서 가장 큰 값을 찾되, 그 이후, 중요한 조건이 하나 있다면 가장 큰 값이 counts 배열 내부에 겹친다면, 그것까지 같이 반환해주어야 한다. 예를 들어 counts[3,3,2] 일때 [3] 만 반환하는 것이 아니라, [3,3] 을 반환해야 한다.

func biggest(counts []int) []int {
	max := math.MinInt8
	biggest := make([]int, 0)

	// 가장 큰 값을 찾는다.
	for _, count := range counts {
		if max < count {
			max = count
		}
	}
	// 가장 큰 값이 몇개가 들어있는지 찾는다.
	for i, count := range counts {
		if max == count {
			biggest = append(biggest, i+1)
		}
	}
	return biggest
}

func TestBiggest(t *testing.T) {
	cases := []struct {
		counts []int
		expect []int
	}{
		{[]int{7, 0, 0}, []int{1}},
		{[]int{2, 2, 2}, []int{1, 2, 3}},
	}
	for _, c := range cases {
		biggest := biggest(c.counts)
		if len(biggest) != len(c.expect) {
			t.Errorf("got %#v, want %#v", biggest, c.expect)
			return
		}
		for i, b := range biggest {
			if b != c.expect[i] {
				t.Errorf("got %#v, want %#v", biggest, c.expect)
			}
		}
	}
}

func solution(answers []int) []int

자 이제, 이 문제를 어떻게 풀어내는지 살펴보면 된다. 먼저 *p 타입을 갖는 persons 슬라이스에 3명의 수포자를 정의하고, answers 를 돌면서 p.resolve() 메서드를 통해 내부적으로 p.count 를 쌓는다. 그 다음, biggest 함수로 가장 큰 값을 찾아 리턴하면 된다.

func solution(answers []int) []int {
	persons := []*p{
		{[]int{1,2,3,4,5}, 0, 0},
		{[]int{2,1,2,3,2,4,2,5}, 0, 0},
		{[]int{3,3,1,1,2,2,4,4,5,5}, 0, 0},
	}
	counts := make([]int, 0)

	for _, answer := range answers {
		for _, p := range persons {
			p.resolve(answer)
		}
	}

	for _, p := range persons {
		counts = append(counts, p.count)
	}

	return biggest(counts)
}

func TestSolution(t *testing.T) {
	cases := []struct {
		answers []int
		expect  []int
	}{
		{[]int{1, 2, 3, 4, 5}, []int{1}},
		{[]int{1, 3, 2, 4, 2}, []int{1, 2, 3}},
	}
	for _, c := range cases {
		biggest := solution(c.answers)
		if len(biggest) != len(c.expect) {
			t.Errorf("got %#v, want %#v", biggest, c.expect)
			return
		}
		for i, b := range biggest {
			if b != c.expect[i] {
				t.Errorf("got %#v, want %#v", biggest, c.expect)
			}
		}
	}
}

더 읽을거리

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

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