[프로그래머스] 모의고사 (완전탐색 Lv. 1) - 자바 Java

1. 문제 설명 (출처 : 프로그래머스)

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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은 모든 문제를 틀렸습니다.
  • 따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.
• 입출력 예 #2
  • 모든 사람이 2문제씩을 맞췄습니다.

 

 

2. 문제 접근 방식 (문제 단순화 하기)

• 늘 그렇듯, 문제를 간단하게 만들어보는 것이 1단계이다.
• 완전 탐색 유형은 가장 단순하고 그래서 참 쉽다.
• 하나도 빠짐없이 모든 경우의 수를 확인하고 있는지만 확인하면 된다.
• 이 문제의 경우에는 각 수포자가 제출한 답안이, 실제 정답지와 몇 개 맞는지를 세면 되는 아주 간단한 문제이다.

3. 완전 탐색 솔루션

import java.util.*;

class Solution {
    public static int[] solution(int[] answers) {
        int[][] patterns = {
                {1, 2, 3, 4, 5},
                {2, 1, 2, 3, 2, 4, 2, 5},
                {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
        };

        // 1. Count correct count per person
        int[] hit = new int[3];
        for(int personIdx = 0; personIdx < hit.length; personIdx++) 
            for(int probIdx = 0; probIdx < answers.length; probIdx++) 
                if(patterns[personIdx][probIdx % patterns[personIdx].length] == answers[probIdx]) 
                    hit[personIdx]++;

        // 2. Find Max Count
        int max = Math.max(hit[0], Math.max(hit[1], hit[2]));
        
        // 3. Find Max Players
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < hit.length; i++)
            if(max == hit[i]) 
                list.add(i + 1);

        // 4. Make answer array
        int[] answer = new int[list.size()];
        int cnt = 0;
        for(int num : list)
            answer[cnt++] = num;
        return answer;
    }
}

1) 각 사람 별 정답 수 계산하기

• 이 이중 루프는 personIdx와 probIdx별로 전부 돌면서 각 사람이 몇 개의 문제를 맞혔는지 계산하는 동작을 수행한다.
• 이 동작이 끝난 뒤의 hit 배열은 다음과 같은 모습이 된다. (1번 예제 기준)

예제 1번 기준 hit 배열 모습

2) hit[0], hit[1], hit[2] 중 max값 찾기

• 정답자 중 max 값을 확인해야만, max 값인 정답자들을 전부 반환할 수 있기 때문에 최댓값을 확인한다.
• 이 경우 max == 5가 된다.
• Math.max(a, b) : a와 b 중 더 큰 값을 반환해주는 함수이다.

3) Max값과 동일한 값을 가진 사람 찾기

• 이제 다시 hit 배열을 돌며 max값과 동일한 정답 수를 가진 사람을 찾아 list에 추가한다.
• 이렇게 해야만 max값으로 동점을 가진 사람을 전부 찾을 수 있게 된다.

4) 배열 형태로 변환하여 반환하기

• List는 추가/제거가 용이하여 개수가 정해지기 전에 사용하기 좋다.
• 하지만 답안은 배열 형태로 반환해야 되기 때문에 다시 배열로 변환해줘야 한다.
• 코드에서 보듯 List의 값을 하나씩 꺼내서 담아줄 수도 있지만, stream을 사용하여 다음과 같이 한 번에 변환할 수도 있다.
• 스트림은 '데이터의 흐름’입니다. 배열 또는 컬렉션 인스턴스에 여러 함수를 조합하여 원하는 결과를 필터링하고 가공된 결과를 얻을 수 있습니다.
• 또한 람다를 이용하여 코드를 간소화할 수 있습니다.

return list.stream().mapToInt(i->i.intValue()).toArray();

• list.stream() : 기존의 Integer List를 IntegerStream으로 변환하는 함수
• i -> i.intValue() : i라는 Integer 타입 변수가 있을 때, i.intValue() 형태로 primitve int 값을 추출하는 람다
  • 람다란 한 줄짜리 간단한 함수(?) 정도로 이해하면 된다.
• list.stream().mapToInt(i->i.intValue()) : Integer List를 IntegerStream으로 변환하고, 해당 리스트의 모든 Integer 타입 값을 하나씩 (흐름으로) 람다를 태운다. 즉, Integer List의 모든 값을 int 형태 primitve 변수로 변환하여 그 '데이터 흐름'을 반환한다.
• list.stream().mapToInt(i->i.intValue()).toArray() : 바로 윗 단계에서 반환된 int 타입의 데이터 흐름을 Array로 변환한다.
• List에서 하나씩 get 하여 array에 담는 코드가 작성하기 쉽다는 장점이 있지만 코드가 길어진다면,
  stream은 한 줄로 동일한 동작을 하여 코드가 매우 간결하지만, 생각보다 어려워하는 경우도 있다. 

 

4. 참 쉽죠?

• 완전 탐색은 참 쉽다. 빠짐없이 모든 경우의 수를 다 따져보기만 하면 되는데, 컴퓨터는 이런 것을 하는 데 최적화되어있는 존재다.
• 이게 코딩 테스트 문제로 나와 한 사람의 취직을 결정하는 문제가 되기는 어렵지만,
  이 정도 수준의 문제를 단순 버그 없이 한 번에 짤 수 있는지는 나의 구현 능력을 가늠하는 간단한 평가 정도는 될 것 같다.
• 이런 문제 조차 한 번에 pass를 해내지 못한다면, 뛰어난 수학적 사고가 있다 할지라도 구현 능력이 부족하다는 것을 의미하니, 같은 문제라도 반복해서 풀며 한 번에 맞출 때까지 도전해 보는 것도 의미가 있다고 생각한다.