문제 출처
문제 출처 : 모의고사
문제 이해하기
문제를 읽어보면 알겠지만, 이해하기 위해 굉장히 많은 노력이 필요로 하는 문제는 아니다. 1번 문제부터 마지막 문제까지의 정답이 순서대로 담긴 배열 answer과 1번 수포자가 찍는 방식, 2번 수포자가 찍는 방식, 3번 수포자가 찍는 방식을 다 비교하여 가장 많은 문제를 맞힌 학생을 찾는 것이다.
만약 학생이 1명 이상이라면 순서대로 출력해 주면 끝나는 문제이다.
주요 조건 이해하기 ⭐️
조심해야 하는 부분은 시험이 최대 10,000 문제로 구성되어 있다는 점이다.
이 말은 시간 복잡도가 O(n^2) 걸리는 방법으로 풀면 1초를 초과하기 때문에 시간 제한 오류를 만날 가능성이 크다.
사실 문제를 완전히 이해했다면 O(n^2) 방법으로 풀지 않아도 된다는 것을 알 수 있다.
여기서 중요한 것은 1번 수포자, 2번 수포자, 3번 수포자들은 특정 패턴을 가지고 답을 찍는 것을 알 수 있다. 하지만 수포자별로 반복되는 패턴의 갯수가 다르다.
- 1번 수포자는 1, 2, 3, 4, 5 총 5개의 숫자가 반복적으로 나타난다.
- 2번 수포자는 2, 1, 2, 3, 2, 4, 2, 5 총 8개의 숫자가 반복적으로 나타난다.
- 3번 수포자는 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 총 10개의 숫자가 반복적으로 나타난다.
여기까지 각 수포자들의 반복적인 규칙을 찾았다면 아래와 같이 배열을 초기화해서 만들 수 있다.
int[] first = {1, 2, 3, 4, 5}; // 5개씩 반복
int[] second = {2, 1, 2, 3, 2, 4, 2, 5}; // 8개씩 반복
int[] third = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 10개 반복이 후 들어오는 answer 배열과 각각 수포자 배열마다 정답 일치여부를 판별만 하면 되는데 문제는 각 수포자별로 반복되는 갯수가 서로 다르다. 그렇다면 어떻게 비교해야하는지 고민할 것이다.
이 문제를 풀었을 당시 필자는 아래의 2가지 방법을 고민했었다.
- 각 수포자배열을 최대 10,000개씩 생성한다?
- 인덱스와 각 수포자의 반복되는 수의 갯수와 나누면 어떻게 될 것 같다?
첫번째 고민은 사실상 말도 안되고, 만드는 방법도 모르겠다 🥹
두번째 고민을 가지고 생각을 해보니 충분히 가능성이 있을 것 같다는 느낌이 들었다.
아래의 샘플 코드를 실행해보자
// a % b --> 왼쪽 피연산자를 오른쪽 피연산자로 나눈 나머지 값을 구함
for (int i = 0; i < 10; i++) {
System.out.println("1번 수포자 : " + i % 5);
System.out.println("2번 수포자 : " + i % 8);
System.out.println("3번 수포자 : " + i % 10);
System.out.println("------------------------");
}이 코드를 실행해보면 이러한 결과가 나타난다.
1번 수포자 : 0
2번 수포자 : 0
3번 수포자 : 0
------------------------
1번 수포자 : 1
2번 수포자 : 1
3번 수포자 : 1
------------------------
1번 수포자 : 2
2번 수포자 : 2
3번 수포자 : 2
------------------------
1번 수포자 : 3
2번 수포자 : 3
3번 수포자 : 3
------------------------
1번 수포자 : 4
2번 수포자 : 4
3번 수포자 : 4
------------------------
1번 수포자 : 0
2번 수포자 : 5
3번 수포자 : 5
------------------------
1번 수포자 : 1
2번 수포자 : 6
3번 수포자 : 6
------------------------
1번 수포자 : 2
2번 수포자 : 7
3번 수포자 : 7
------------------------
1번 수포자 : 3
2번 수포자 : 0
3번 수포자 : 8
------------------------
1번 수포자 : 4
2번 수포자 : 1
3번 수포자 : 9
------------------------반복문에서 사용되는 변수 i를 각 수포자의 반복 갯수로 나눈 나머지를 계산해보면
첫번째 수포자는 5를 넘어가는 순간 다시 0으로 변경되어 시작된다.
두번째 수포자는 8를 넘어가는 순간 다시 0으로 변경되어 시작된다.
세번째 수포자는 10을 넘어가는 순간 다시 0으로 변경되어 시작된다.이러한 규칙을 찾았다면 문제가 최대 10,000개 와도 끄떡없이 풀 수 있게 된다.
이를 바탕으로 제일 많이 맞힌 학생을 찾을 수 있다.
int[] first = {1, 2, 3, 4, 5}; // 5개씩 반복
int[] second = {2, 1, 2, 3, 2, 4, 2, 5}; // 8개씩 반복
int[] third = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 10개 반복
int[] answer = {0, 0, 0}; // 학생별 정답의 맞힌 수를 저장하는 배열
for (int i = 0; i < answers.length; i++) {
if (answers[i] == first[i % 5]) answer[0]++;
if (answers[i] == second[i % 8]) answer[1]++;
if (answers[i] == third[i % 10]) answer[2]++;
}이렇게까지 구하면 제일 많이 맞힌 학생을 찾을 순 있지만, 문제 제한 조건 중 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순으로 정렬해주세요 라는 조건이 존재한다.
코드를 작성하기전에 해야할 일을 정리해보면
- 가장 먼저 해야 할 일은 최대값을 구하는 일이다.
- 최종적으로 결과를 출력할 배열을 생성해준다. (필자의 경우 ArrayList를 사용했다.)
- 최대값을 구한 후 answer 배열을 순회하면서 최대값과 일치하는 학생이 있다면 출력할 배열에 값을 하나씩 추가해준다.
엇! 답이 만약 1개인 경우는 굳이 배열이 필요없지 않을까? 라는 생각을 조금이라도 할 수 있겠지만, 문제에 나와있는 경우를 제외한 나머지 경우 또한 우리가 예측할 수 없기 때문에 바로 위에 설명해놓은 로직을 꼭 작성해야한다.
제출 코드
import java.util.*;
class Solution {
public int[] solution(int[] answers) {
int[] first = {1, 2, 3, 4, 5}; // 5개씩 반복
int[] second = {2, 1, 2, 3, 2, 4, 2, 5}; // 8개씩 반복
int[] third = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 10개 반복
int[] answer = {0, 0, 0};
for (int i = 0; i < answers.length; i++) {
if (answers[i] == first[i % 5]) answer[0]++;
if (answers[i] == second[i % 8]) answer[1]++;
if (answers[i] == third[i % 10]) answer[2]++;
}
// 최대값 구하기
int maxScore = Math.max(answer[0], Math.max(answer[1], answer[2]));
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < answer.length; i++) {
if (answer[i] == maxScore) {
list.add(i + 1);
}
}
return list.stream().mapToInt(i -> i).toArray();
}
}