모의고사
문제 설명
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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
에 대해 대응을 해줄 필요가 있다.
i
는 pattern
배열에 대한 인덱스다. 반복문을 통해 패턴을 반복하고 나면, 다시 처음으로 되돌아가 패턴을 다시 검증해줄 필요가 있는데, 만약 인덱스가 배열의 마지막 인덱스에 되돌아가면 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