[Java] Climbing the Leardboard - HackerRank BinarySearch

문제 링크

Climbing the Leaderboard | HackerRank

 

 

 

요약

ranked와 player배열이 있는데, ranked 배열은 기존의 리더보드, player배열은 플레이어의 점수.

리더보드의 랭킹과 player를 비교해서 player의 랭킹을 출력하는 문제.

 

ranked는 내림차순 정렬, player는 오름차순 정렬로 주어짐

 

 

 

 

풀이

문제 조건에서, player와 ranked의 길이가 2x10^5까지로 주어졌고,  겹치는 숫자가 존재할 수 있기 때문에

ranked를 HashSet으로 중복 제거 및 재정렬 해주었다.

 

그런 다음 그냥 binary search를 이용해서 풀어냈다. (O(nlogm))

 

여기서 주의할점은, 리더보드의 가장 낮은 등수의 점수보다 player의 점수가 더 낮은경우, 리더보드의 순위보다 더 아래의 등수로 입력되어야 한다. 그렇기 때문에 등수 하나를 더 더해주는 것을 잊지 말자

(내 코드를 보고 헷갈릴 수 있기 때문에 남기는 설명 : 배열 idx는 0부터, 등수는 1부터기 때문에 mid+2, mid+1을 해주었음.)

public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
// Write your code here
    Set<Integer> set = new HashSet<>(ranked);
    ranked = new ArrayList<>(set);
    Collections.sort(ranked, Collections.reverseOrder());

    List<Integer> list = new ArrayList<>();

    for(int p : player) {
        int left = 0;
        int right = ranked.size()-1;
        int mid = 0;    

        while(left<=right) {
            mid = (left+right)/2;
            if(p == ranked.get(mid)) break;

            if(p > ranked.get(mid)) right = mid-1;
            else left = mid +1;                
        }

        if(p < ranked.get(mid)) list.add(mid+2);
        else list.add(mid+1);        
    }

    return list;
}