로또의 최고 순위와 최저 순위

<풀기 전 생각>

핵심적으로 해야 할 것은 win_nums의 배열의 저장된 정수를 lottos에 몇개 나 가지고 있는지 탐색 하는 것 임으로

단순 반복으로 선형 탐색하여 해결 할 수도 있겠지만 O(n) 이진탐색 + 정렬 O(2log n)을 통해 속도를 더 개선시키자는 생각으로 문제 풀이에 들어갔다.

 

<중간 문제점>

단순히 Arrays.binarySearch(win_nums, lottos[i]) > -1 내장된 빌트인 함수를 사용할 수도 있겠지만

앞에 0의 갯수를 감안하여 이진 탐색의 범위를 좁히고 싶어 직접 구현하게 되었다.

 

<최종적인 코드>

class Solution {
    // 시간 복잡도 O(nlog n) 공간 복잡도 O(n)
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        Arrays.sort(win_nums);
        int zeroCount = 0;
        int correctCount = 0;
        // 0의 갯수 체크
        for (int lotto: lottos) {
            if(lotto==0)
                zeroCount++;
            else
                break;
        }

        // 로또 번호 탐색 시작
        for (int num:win_nums) {
            int first = zeroCount;
            int last = lottos.length-1;
            // 이진 탐색
            while(first<=last){
                int mid = (first+last)/2;
                if(lottos[mid]>num)
                    last = mid-1;
                else if(lottos[mid]<num)
                    first = mid+1;
                else {
                    correctCount++;
                    break;
                }
            }
        }

        int maxCorrect = zeroCount+correctCount;
        int maxRank = 7-maxCorrect;
        answer[0] = maxRank>=6?6:maxRank;

        int minRank = 7-correctCount;
        answer[1] = minRank>=6?6:minRank;

        return answer;
    }
}

<메모> 

우수 풀이를 보니 Map 자료구조의 containsKey() 시간 복잡도 O(1) 함수를 활용하여 지금 내가 짠 코드의 시간 복잡도 O(nlog n) 보다 더 효율적으로 O(n)으로 푼 풀이를 볼 수 있어서 

중복을 제외한(중요!) 두 배열에서 겹치는 요소를 탐색 할 때는 Mep or Set의 자료구조를 활용해야 겠다.