[프로그래머스] 모의고사 (JAVA)

링크

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

프로그래머스

 

문제 요약

수포자 3명이 주어진 패턴으로 정답을 찍고, 정답 리스트 answers가 주어졌을 때 가장 정답을 많이 맞힌 사람을 반환하는 문제입니다.

• 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,...

 

제한

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

 

풀이

가장 쉽게 떠오르는 방식은 정답과 1번, 2번, 3번이 선택한 정답을 한 문제씩 비교하는 방식입니다.

그러면 총 O(3N)=O(N)의 시간복잡도로 문제를 풀 수 있습니다.

1. answers의 i번째 문제 정답과, 1번 2번 3번이 선택한 i번째 문제 정답을 비교한다.
2. 만약 정답이 맞으면 각 수포자의 count 값을 증가시킨다.
3. 정답 비교가 끝난 후, count 값이 동일한 사람이 있으면 오름차순으로 정렬해 고득점자 리스트를 반환한다.

 

추가적으로 생각해야 할 것은 i번째 문제에 대해 세 사람이 어떤 정답을 택했는가입니다.

찍는 방식을 살펴보면 각자 패턴이 있는데, 처음에는 이 패턴을 수학적으로 정의하려 했습니다.

가령, 1번 수포자는 인덱스 i에 대해 (i%5+1)을 선택한다고 할 수 있습니다.

하지만 이와 똑같이 수학적으로 2번, 3번의 정답을 정의하려니 어려움이 있었습니다.

 

그래서 생각한 방법은 일단 각자 반복되는 부분을 배열로 정의해 두고, 이를 인덱싱하여 사용하면 된다는 것입니다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int cnt1=0, cnt2=0, cnt3=0;
        int[] pat1={1,2,3,4,5};
        int[] pat2={2,1,2,3,2,4,2,5};
        int[] pat3={3,3,1,1,2,2,4,4,5,5};
        for(int i=0; i<answers.length; i++){
            if(answers[i]==pat1[i%5]) cnt1++;
            if(answers[i]==pat2[i%8]) cnt2++;
            if(answers[i]==pat3[i%10]) cnt3++;
        }
        ArrayList<Integer> highest = new ArrayList<>();
        int mx = Math.max(Math.max(cnt1,cnt2),cnt3);
        if(cnt1==mx) highest.add(1);
        if(cnt2==mx) highest.add(2);
        if(cnt3==mx) highest.add(3);

        return highest.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

[시간 복잡도]

• N: answers 길이
• answers를 순회하며 3명의 점수를 계산 → O(N)
• 그 이후는 N에 영향을 안 받으므로 상수 복잡도
• 최종 시간 복잡도 = O(N)

[추가]

세 사람의 패턴을 하나의 2차원 배열에 저장하고, cnt 값도 1차원 배열에서 관리한다면 2중 for문으로 만들어 내부의 코드를 더 간결하게 만들 수 있습니다.

• `if(answers [i]==pat [j][i% pat [j]. length]) cnt [j]++;`