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

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

문의는 댓글 바람.

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/77484?language=java

[접근 방법]

로또 번호를 매번 선행순회를 하면서 맞는지 확인하려면 시간복잡도가 O(n^2)이 된다.

로또번호는 중복되지 않으니, HashSet을 이용하여 검색하는 것이 훨씬 빨라보인다. 

HashSet의 경우 값을 해쉬 함수를 이용하여 특정 메모리의 저장하기 때문에, 검색속도는 O(1)이다.

결과적으로 모든 번호를 검색하는데 걸리는 시간은 O(n)이 된다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        Set<Integer> winNumberSet = new HashSet<>();
        for (int win_num : win_nums) {
            winNumberSet.add(win_num);
        }

        int erasedNumberCount = 0;
        int correctNum = 0;
        for (int lotto : lottos) {
            if (lotto == 0) {
                erasedNumberCount++;
                continue;
            }
            if (winNumberSet.contains(lotto)) correctNum++;
        }
        answer[0] = correctNum + erasedNumberCount;
        answer[1] = correctNum;

        for (int i = 0; i < answer.length; i++) {
            switch (answer[i]) {
                case 6:
                    answer[i] = 1;
                    break;
                case 5:
                    answer[i] = 2;
                    break;
                case 4:
                    answer[i] = 3;
                    break;
                case 3:
                    answer[i] = 4;
                    break;
                case 2:
                    answer[i] = 5;
                    break;
                default:
                    answer[i] = 6;
            }
        }
        return answer;
    }
}

 

[내 답안 수정하기]

 

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        Set<Integer> winNumberSet = new HashSet<>();
        //Set의 당첨 번호 넣기
        for (int win_num : win_nums) { winNumberSet.add(win_num); }     

        // 지워진 번호의 개수
        int erasedCnt = 0;
        // 총 지워진 개수와, 지워진 개수를 다 틀렸다고 가정했을 때 맞은 개수 구하기.
        for (int lotto : lottos) {
            if (lotto == 0) erasedCnt++;
            if (winNumberSet.contains(lotto)) answer[0]++;
        }
        // answer[1]은 지워진 숫자는 다 틀렸다고 봤을 때
        answer[1] = answer[0];
        // answer[0]은 지워진 숫자가 다 맞았다고 봤을 때
        answer[0] += erasedCnt;

        // getRanking 메서드를 이용하여, 등수 구하기
        answer[0] = getRanking(answer[0]);
        answer[1] = getRanking(answer[1]);
        return answer;
    }

    // 등수를 리턴하는 메서드
    private int getRanking(int correctCnt) {
        int ranking = 0;
        switch (correctCnt) {
            case 6:
                ranking = 1;
                break;
            case 5:
                ranking = 2;
                break;
            case 4:
                ranking = 3;
                break;
            case 3:
                ranking = 4;
                break;
            case 2:
                ranking = 5;
                break;
            default:
                ranking = 6;
        }

        return ranking;
    }
}