프로그래머스 - 모의고사

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처

코딩테스트 연습 - 모의고사

[문제 설명]

3개의 찍는 패턴이 있을 때, 제일 많이 맞는 패턴을 반환하세요.

 

[처음 생각한 접근 방법]

전에 한 번 풀었던 문제로, 과거 풀었던 코드를 보니 엉망이라 다시 풀어봤습니다.

완전 탐색을 이용한 문제로 재귀를 통해서 풀어보았습니다.

 

[이번에 풀어본 방법]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] solution(int[] answers) {
        int[][] patterns = new int[][]{
            {1,2,3,4,5}
            ,{2,1,2,3,2,4,2,5}
            ,{3,3,1,1,2,2,4,4,5,5}
        };
        List<Integer> list = new ArrayList<>();
        int patternOneResult = recursion(0, patterns[0], answers);
        int patternTwoResult = recursion(0, patterns[1], answers);
        int patternThreeResult = recursion(0, patterns[2], answers);
        int maxNum = Math.max(patternOneResult, Math.max(patternTwoResult,patternThreeResult));
        if (patternOneResult == maxNum) list.add(1);
        if (patternTwoResult == maxNum) list.add(2);
        if (patternThreeResult == maxNum) list.add(3);

        int[] answer = new int[list.size()];
        for (int i = 0;  i < answer.length; i++) answer[i] = list.get(i);
        return answer;
    }

    private int recursion(int index, int[] pattern, int[] answers) {
        if (index == answers.length) return 0;
        int correctNum = 0;
        if (answers[index] == pattern[index%pattern.length]) correctNum++;

        return correctNum + recursion(index+1, pattern, answers);
    }
}

시간복잡도는 아무래도 재귀함수 덕분에 O(n)이 되지 않을까 싶다.

 

[과거에 푼 코드]

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int[] answers) {
        int answer[];
        int[] correctNum = new int[3];
        int[][] pattern = new int[][]{
                {1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5},
                {2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5},
                {3,3,1,1,2,2,4,4,5,5,3,3,1,1,2,2,4,4,5,5,3,3,1,1,2,2,4,4,5,5,3,3,1,1,2,2,4,4,5,5}
        };
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < answers.length; i++) {
            int patternIdx = i%pattern[0].length;
            if (answers[i] == pattern[0][patternIdx]) correctNum[0]++;
            if (answers[i] == pattern[1][patternIdx]) correctNum[1]++;
            if (answers[i] == pattern[2][patternIdx]) correctNum[2]++;
        }

        int max = Math.max(correctNum[0],Math.max(correctNum[1],correctNum[2]));
        for (int i = 0; i < correctNum.length; i++)
            if (correctNum[i] == max) list.add(i);

        answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
            answer[i] = list.get(i) + 1;

        return answer;
    }
}

옛날에 푼 코드는 3 패턴의 최소 공배수를 이용해 푼듯하다. 패턴이 추가 될 수록 최소 공배수를 위한 메모리가 엄청 낭비 되지 않을까 싶다.

오늘 짠 코드도 그렇게 깔끔하다는 생각은 들지 않지만, 확실히 코드가 옛날보다는 깔끔해진 느낌이 든다.