[프로그래머스] 로또의 최고 순위와 최저 순위 for JAVA

 

https://school.programmers.co.kr/learn/courses/30/lessons/77484?language=java 

프로그래머스

 

 

 

 

 

 

---

 

 

숫자가 0인 것을 모두 맞았다고 가정했을 때 최고의 등수, 다 틀렸다고 가정했을 때 최저의 등수인 문제이다.

 

 

import java.util.*;

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        Set<Integer> win_num = new HashSet<>();
        for(int i=0; i<win_nums.length; i++)
            win_num.add(win_nums[i]);
        
        int zero = 0;
        int win = 0;
        for(int lotto : lottos){
            if(lotto == 0) zero += 1;
            else{
                if(win_num.contains(lotto)) win += 1;
            }
        }
        
        answer[0] = Rank(win+zero);
        answer[1] = Rank(win);
        
        return answer;
        
        
    }
    private static int Rank(int num){
        switch(num){
            case 6:
                return 1;
            case 5:
                return 2;
            case 4:
                return 3;
            case 3:
                return 4;
            case 2:
                return 5;
            default:
                return 6;
        }
    }
}

 

Set의 contains는 시간 복잡도가 O(1)이기 때문에

 

2중 for문을 돌렸다면 O(N^2)이었을 시간 복잡도를 O(N)으로 줄였다.

 

 

 

성능

 

 

약 1년전에 풀었던 문제이고 파이썬 한창 공부할 때 파이썬으로도 풀어봤던 문제이다.

 

시간복잡도를 고려하다니 그때에 비하면 많이 발전했구나...

 

아직 멀었지만......................

 

^^

 

 

---

 

 

남의 풀이를 구경하는데 Arrays.binarySearch()를 사용했길래 정리해본다.

 

 

 

 

이진탐색...!

 

이진 탐색으로 배열을 정렬한 뒤 Arrays.binarySearch(배열, 찾으려는 값)을 사용하면 O(logN)의 시간 복잡도를 가진다.

 

값이 존재한다면 자릿값인 양수 값을 리턴할 것이고 0보다 작은 값이 나온다면 존재하지 않는다는 뜻이다.

 

 

 

저 함수를 쓸 생각조차 못했는데 괜찮은 것 같다.