프로그래머스 2021 Dev-Matching 로또의 최고 순위와 최저 순위

프로그래머스 2021 Dev-Matching - 로또의 최고 순위와 최저 순위

1. lottos 에서 0 개수를 알아낸다. (int zeroCnt)
2. lottos 에서 0을 제외하고 win_nums 와 곂치는 숫자의 개수를 알아낸다. (int winCnt)
3. zeroCnt과 winCnt을 이용하여 등수를 알아낸다.

첫 번째 풀이

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];

        // 1. lottos 에서 0 개수를 알아낸다. (int zeroCnt)
        int zeroCnt = 0;
        for(int n : lottos) {
            if(n == 0) zeroCnt++;
        }
        // 2. lottos 에서 0을 제외하고 win_nums 와 곂치는 숫자의 개수를 알아낸다. (int winCnt)
        int winCnt = 0;
        for(int n : win_nums) {
            for(int m : lottos) {
                if(n == m) winCnt++;
            }
        }
        // 3. zeroCnt과 winCnt을 이용하여 등수를 알아낸다.
        answer[0] = 7 - (winCnt + zeroCnt);
        answer[1] = 7 - winCnt;

        if(winCnt == 0){
            answer[1] = 6;
            if(zeroCnt == 0) answer[0] = 6;
        }
        return answer;
    }
}

2번에서 당첨번호를 확인하는데에 N^2 의 시간이 걸린다.

(문제 특성상 어차피 N은 항상 6이지만 그래도 좀 더 고민해보자)

두 번째 풀이

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
         
         // 1. lottos 에서 0 개수를 알아낸다. (int zeroCnt)
        int zeroCnt = 0;
        Set<Integer> set = new HashSet<>();
        for(int n : lottos) {
            set.add(n);
            if(0 == n)  zeroCnt++;
        }
        // 2. lottos 에서 0을 제외하고 win_nums 와 곂치는 숫자의 개수를 알아낸다. (int winCnt)
        int winCnt = 0;
        for(int n : win_nums) {
            if(set.contains(n)) winCnt++;
        }
        // 3. zeroCnt과 winCnt을 이용하여 등수를 알아낸다.
        answer[0] = 7 - (winCnt + zeroCnt);
        answer[1] = 7 - winCnt;

        if(winCnt == 0){
            answer[1] = 6;
            if(zeroCnt == 0) answer[0] = 6;
        }
        return answer;
    }
}

2번에서 Set을 이용해 당첨번호를 확인하도록 수정했다.

Java HashSet에서 contains 함수는 검색하는데 일반적으로 O(1) 의 시간이 걸린다고 한다. 참고

+더 알아보기 : Java Collections - Set

3번에서 등수를 알아낼 때 lottos가 모두 0이거나, 0이 없고 모두 win_nums랑 다른 경우를 if문을 이용해 처리했다.

운좋게 반례가 생각이나서 if문으로 처리했지만 좋아보이지 않는다.

세 번째 풀이

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];

         // 1. lottos 에서 0 개수를 알아낸다. (int zeroCnt)
        int zeroCnt = 0;
        Set<Integer> set = new HashSet<>();
        for(int n : lottos) {
            set.add(n);
            if(0 == n)  zeroCnt++;
        }
        // 2. lottos 에서 0을 제외하고 win_nums 와 곂치는 숫자의 개수를 알아낸다. (int winCnt)
        int winCnt = 0;
        for(int n : win_nums) {
            if(set.contains(n)) winCnt++;
        }
        // 3. zeroCnt과 winCnt을 이용하여 등수를 알아낸다.
        int[] rank = new int[]{6,6,5,4,3,2,1};

        answer[0] = rank[zeroCnt + winCnt];
        answer[1] = rank[winCnt];

        return answer;
    }
}

3번에서 스터디원의 조언을 듣고 rank배열을 만들어 등수를 계산하도록 수정했다.

특정 케이스마다 if문으로 예외처리해주는 것보다 훨씬 깔끔하고 확장성있어 보인다.

배열의 인덱스는 당첨번호의 개수, 배열의 값은 등수를 나타낸다.

네 번째 풀이

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];

        boolean[] isWin = new boolean[46]; // 로또 6/45

        int zeroCnt = 0;
        int winCnt = 0;

        for(int n : win_nums) isWin[n] = true;
        for(int n : lottos) {
            // 1. lottos 에서 0 개수를 알아낸다. (int zeroCnt)
            if(n == 0) zeroCnt++;
            // 2. lottos 에서 0을 제외하고 win_nums 와 곂치는 숫자의 개수를 알아낸다. (int winCnt)
            else if(isWin[n]) winCnt++;
        }

        // 3. zeroCnt와 winCnt를 이용하여 등수를 알아낸다.
        int[] rank = new int[]{6,6,5,4,3,2,1};

        answer[0] = rank[zeroCnt + winCnt];
        answer[1] = rank[winCnt];

        return answer;
    }
}

2번에서 스터디원의 조언을 듣고 Set이 아니라 배열을 이용해 당첨번호를 확인하도록 수정했다.

배열 인덱스로 표현할 수 없는 범위일때 (배열 인덱스는 integer 범위에서 사용가능, 보통 몇백만 넘으면) 주로 Set을 사용하고, 이외에는 Set 말고 배열로 표현하는게 더 좋다고 한다.

이유는 다음과 같다.

1. 검색속도에 있어서 시간복잡도 똑같이 O(1)이라도 Hash값을 계산해야하는 HashSet보다 메모리 주소에 바로 접근가능한 배열이 좀 더 빠르다.
2. HashSet의 검색속도가 O(1)인 건 데이터양이 적었을 때이며, 데이터가 늘어날 수록 메모리랑 수행시간이 느려진다. 참고(Hash)

+비슷한 다른 문제에서 이와 같은 방식으로 배열을 이용하면 단지 데이터의 존재여부뿐만 아니라 중복데이터의 Count도 확인할 수 있다는 것을 알아두면 좋다.

문제에 따라 적절한 자료구조를 사용할 수 있도록 고민하자!