[HackerRank] Climbing the Leaderboard 알고리즘 풀이

문제설명

점수판은 가장 높은 플레이어 순으로 순위가 매겨집니다.

동등한 점수를 받은 플레이어는 동일한 순위 번호를 받고 다음 플레이어는 바로 다음 순위의 번호를 받습니다. 점수판 n개의 배열 ( 100, 90, 90, 70, 50, 25, 10 ) 과 엘리스의 점수 m개의 배열( 5, 50, 75, 150 )이 제공될 때 엘리스의 각각 점수의 순위를 구하시오.

조건

• 1 <= n <= 2 * 10 ^ 5

• 1 <= m <= 2 * 10 ^ 5

• 점수판은 내림차순으로 정렬되어있음

• 엘리스의 점수는 오름차순으로 정렬되어있음

난이도

• Medium

점수판

순위	이름	점수
1	User1	100
2	User2	90
2	User3	90
3	User4	70
4	User5	50
5	User6	25
6	User7	10

엘리스 점수

5

50

75

150

•  엘리스 점수 5점일 경우

순위	이름	점수
1	User1	100
2	User2	90
2	User3	90
3	User4	70
4	User5	50
5	User6	25
6	User7	10
7	Alice	5

•  엘리스 점수 50점일 경우

순위	이름	점수
1	User1	100
2	User2	90
2	User3	90
3	User4	70
4	User5	50
4	Alice	50
5	User6	25
6	User7	10

•  엘리스 점수 75점일 경우

순위	이름	점수
1	User1	100
2	User2	90
2	User3	90
3	Alice	75
4	User4	70
5	User5	50
6	User6	25
7	User7	10

•  엘리스 점수 150점일 경우

순위	이름	점수
1	Alice	150
2	User1	100
2	User2	90
3	User3	90
4	User4	70
5	User5	50
6	User6	25
7	User7	10

최종 엘리스 순위 결과

7

4

3

1

풀이과정

처음에는 점수판에서 엘리스의 점수를 하나씩 순차비교하여 순위를 구했습니다.

하지만 결국 timeout이 발생했습니다. 이중 for문으로 인해 시간복잡도가 O(n^2)가 나와서 

모든 케이스를 만족하지 못했던 것 같습니다. 틀린 케이스 중 한개의 Input과 output을 확인해보았는데

점수판의 점수와 엘리스의 점수가 각각 20만개이고 문제에 나와있듯이 점수판은 내림차순, 엘리스는 오름차순이므로 순차탐색으로 접근할 경우 중간 부분을 제외하고는 최악의 시간이 나올 수 밖에 없었습니다.

어떻게해야 최적의 시간으로 정답을 구할 수 있을까 고민해보다가 이진트리를 사용하여 해결해보기로 했습니다.

TreeSet은 이진탐색트리(BinarySearchTree)의 형태로 데이터를 저장하는 Collection 입니다.

이진탐색트리 중에서도 성능을 향상시킨 '레드-블랙 트리(Red-Black Tree)로 구현되어 있습니다.

1. 이진트리에 중복없이 저장  O(n)

2. 오름차순으로 정렬  O(n)

3. Map을 이용해 점수 순위 저장 O(n)

4. 이진트리를 탐색하여 엘리스의 점수가 몇등인지 저장 O(n log n)

/*
     * Complete the climbingLeaderboard function below.
     */
    static int[] climbingLeaderboard(int[] scores, int[] alice) {
        /*
         * Write your code here.
         */
        int[] ranks = new int[alice.length];
        TreeSet<Integer> treeSet = new TreeSet<>();
        for(int i : scores) treeSet.add(i);
        NavigableSet<Integer> decendingSet = treeSet.descendingSet();
        HashMap<Integer, Integer> map = new HashMap<>();
        int rank = 1;
        Iterator iter = decendingSet.iterator();
        while(iter.hasNext()) map.put((Integer)iter.next(), rank++);
        
        for(int i = 0; i < alice.length; i++) {
            int as = alice[i];
            if(as > decendingSet.first()) {
                ranks[i] = 1;
                continue;
            }
            if(as < decendingSet.last()) {
                ranks[i] = map.get(decendingSet.last()) + 1;
                continue;
            }
            ranks[i] = map.get(decendingSet.ceiling(as));
        }
        return ranks;
    }

출처

해커랭크 Climbing-the-leaderboard 문제풀러가기