[HackerRank] Climbing the Leaderboard

1. Problem

• https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

2. Feedback

• 주어진 점수의 랭킹이 몇 등인지 구하는 문제
• 정렬되있다는 힌트를 보고 이진 검색을 생각했고, 랭킹을 구하기 위해 이진검색을 변형시켜서 풀었음.
• 순위를 매기는 작업은 시간복잡도 O(n)
• 이진검색은 n 을 1/2 씩 줄여나가니 logN
• 총 시간복잡도는 m개의 score 의 순위를 구하는 문제이니 O(n) + O(m*logm)
• min > max 인 부분을 체크를 못해서 시간 걸림.

3. Source

import java.util.Scanner;

public class ClimbingTheLeaderboard {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int score[] = new int[n];
        for (int i = 0; i < n; i++)
            score[i] = in.nextInt();
        int m = in.nextInt();
        int aliceScore[] = new int[m];
        for (int j = 0; j < m; j++)
            aliceScore[j] = in.nextInt();

        int result[] = solve(score, aliceScore);

        for (int k = 0; k < result.length; k++)
            System.out.println(result[k]);
    }

    public static int[] solve(int score[], int aliceScore[]) {
        int result[] = new int[aliceScore.length];

        int rank[] = new int[score.length];
        rank[0] = 1;
        int rankNum = 1;
        for (int i = 1; i < score.length; i++) {
            if (score[i - 1] == score[i])
                rank[i] = rankNum;
            else {
                rankNum++;
                rank[i] = rankNum;
            }
        }

        for (int i = 0; i < aliceScore.length; i++) {
            result[i] = binarySearch(score, rank, aliceScore[i], 0, score.length - 1);
        }
        return result;
    }

    public static int binarySearch(int score[], int rank[], int key, int min, int max) {
        if (min >= max) {
            if (key < score[min]) {
                return rank[min] + 1;
            } else if (key > score[min]) {
                if (min == 0) return 1;
                return rank[min];
            } else {
                return rank[min];
            }
        }

        int mid = (min + max) / 2;

        if (key == score[mid])
            return rank[mid];
        else if (key > score[mid])
            return binarySearch(score, rank, key, min, mid - 1);
        else if (key < score[mid])
            return binarySearch(score, rank, key, mid + 1, max);
        else
            throw new IllegalStateException("IllegalState...");
    }
}