[Algorithm: 완전탐색] 프로그래머스 <모의고사>

문제

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

프로그래머스

 

문제 설명

수포자 3명이 문제를 찍는 방식으로 시험을 본다.
각 학생은 일정한 패턴으로 답을 반복하며 문제를 풀고, 실제 정답 배열 answers가 주어질 때 가장 많은 문제를 맞힌 학생을 구하는 문제이다.

학생들의 찍는 패턴은 다음과 같다.

학생패턴

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

가장 많은 문제를 맞힌 학생을 오름차순 배열로 반환해야 한다.

 

처음 접근과 고민

문제를 읽으면서 먼저 눈에 들어온 점은 다음 두 가지이다.

1. 학생 수는 3명으로 고정되어 있다.
2. 각 학생은 정해진 패턴으로 답을 반복한다.

따라서 하나의 복잡한 로직으로 처리하기보다는 각 학생의 패턴을 배열로 정의하고 비교하는 방식으로 접근하는 것이 가장 단순한 방법이라고 판단했다.

전체 해결 흐름은 다음과 같다.

1. 각 학생의 찍는 패턴을 배열로 정의한다.
2. answers 배열을 순회하면서 각 학생이 맞춘 문제 수를 계산한다.
3. 가장 많이 맞힌 학생을 찾아 결과를 반환한다.

 

 

문제 풀이

먼저 학생들의 패턴을 배열로 정의한다.

int[] student1 = {1, 2, 3, 4, 5};
int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

 

각 학생이 맞춘 문제 수를 저장하기 위해 배열을 하나 생성한다.

int[] studentCnt = new int[3];

 

이후 answers 배열을 순회하면서 각 학생의 패턴과 비교한다.

학생의 패턴 길이는 정답 배열보다 짧기 때문에 패턴을 반복시키기 위해 나머지 연산(%)을 사용한다.

for (int i = 0; i < answers.length; i++) {

    if (answers[i] == student1[i % student1.length]) {
        studentCnt[0]++;
    }

    if (answers[i] == student2[i % student2.length]) {
        studentCnt[1]++;
    }

    if (answers[i] == student3[i % student3.length]) {
        studentCnt[2]++;
    }
}

 

최대값 찾기

각 학생이 맞춘 문제 수는 studentCnt 배열에 저장된다.

studentCnt[0] → 1번 학생
studentCnt[1] → 2번 학생
studentCnt[2] → 3번 학생

 

처음에는 모든 경우의 수를 비교해야 하나 고민했지만, Math.max()를 활용하면 최대값을 간단히 구할 수 있다.

int maxNumber = Math.max(Math.max(studentCnt[0], studentCnt[1]), studentCnt[2]);

 

이후 최대값과 동일한 학생을 찾아 결과 리스트에 추가한다.

 

for (int i = 0; i < studentCnt.length; i++) {
    if (studentCnt[i] == maxNumber) {
        answer.add(i + 1);
    }
}

i + 1을 하는 이유는 배열 인덱스는 0부터 시작하지만, 학생 번호는 1번부터 시작하기 때문이다.

 

최종 코드

import java.util.*;

class Solution {
    public List<Integer> solution(int[] answers) {
        List<Integer> answer = new ArrayList<>();
        
        int[] student1 = {1, 2, 3, 4, 5};
        int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        
        int[] studentCnt = new int[3];
        
        int cnt = 0;
        
        for (int i=0; i< answers.length; i++) {
            if (answers[i] == student1[i % student1.length]) {
                studentCnt[0]++;
            }
            
            if (answers[i] == student2[i % student2.length]) {
                studentCnt[1]++;
            }
            
            if (answers[i] == student3[i % student3.length]) {
                studentCnt[2]++;
            }
        }
        
        System.out.println(studentCnt[0] + " " + studentCnt[1] + " " + studentCnt[2]);
        
        int MaxNumber = Math.max(Math.max(studentCnt[0], studentCnt[1]), studentCnt[2]);
        for (int i=0; i< studentCnt.length; i++) {
            if (studentCnt[i] == MaxNumber) {
                answer.add(i + 1);
            }
        }
        
        return answer;
    }
}

 

 

정리

이 문제의 핵심 포인트는 다음 두 가지이다.

1. 반복되는 패턴 처리 → 나머지 연산(%) 활용
2. 최대값 찾기 → Math.max() 활용

배열과 반복문, 나머지 연산만으로 해결할 수 있는 비교적 단순한 구현 문제이다.