Climbing the Leaderboard(해커랭크, Java)

문제링크: https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

Climbing the Leaderboard | HackerRank

 

알고리즘 설명:

scores의 랭크들을 rank배열을 만들어 scores값들의 랭크를 관리했고 그 뒤 alice를 받아 scores값들과 비교했고 alice의 값이 scores의 값보다 크면 scores의 rank값을 result 배열(결과값이 들어가는 배열)에 넣었다.

 

막혔던 지점:

단순히 2중 for문을 가지고 알고리즘을 짰더니 time limit에 걸려 테스트 케이스가 전부 성공으로 돌아가지 않았다.

즉 가장 시간이 오래걸리는 scores와 alice 값을 비교하는 부분의 탐색방법을 바꿔야 했다.

그래서 2중 for문 대신 퀵정렬에서의 탐색방법을 가져와 알고리즘을 짰고 문제해결을 하였다.

 

public class Solution {

    // Complete the climbingLeaderboard function below.
    static int[] climbingLeaderboard(int[] scores, int[] alice) {
        int start;
        int end;
        int pivot;

        int[] rank = new int[scores.length];
        int level = 2;
        rank[0] = 1;
        int[] result = new int[alice.length];

        //scores는 내림차순으로 정렬되어 있으므로 scores[0]에 rank 1를 주고 level은 2부터 시작
        //다음 값과 전 값을 비교했을 때 값이 같다면 level에서 -1를 해주고 rank 부여
        for(int i =1;i<scores.length;i++){
            if(scores[i]==scores[i-1]) level--;
            rank[i] = level++;
        }

        for(int i=0;i<alice.length;i++){
            int val = alice[i];

            start =0;
            end = scores.length-1;
            pivot = end/2;

            while(start<=end){
                if(scores[pivot]<val){

                    //-1을 한 이유는 pivot까지는 비교가 완료되었기 때문
                    end=pivot-1;

                    //값을 못찾게 되는 경우 rank[pivot] 즉 rank 1값을 넣어줌
                    result[i]=rank[pivot];

                    pivot=(end+start)/2;
                    
                }
                else if(scores[pivot]>val){

                    //+1을 한 이유는 pivot까지는 비교가 완료되었기 때문
                    start=pivot+1;

                    //값을 못찾게 되는 경우 rank[pivot]+1 즉 꼴찌 rank값을 넣어줌
                    result[i]=rank[pivot]+1;

                    pivot=(end+start)/2;
                    
                }
                else{
                    result[i]=rank[pivot];
                    break;
                }
            }
        }

        return result;

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int scoresCount = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[] scores = new int[scoresCount];

        String[] scoresItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < scoresCount; i++) {
            int scoresItem = Integer.parseInt(scoresItems[i]);
            scores[i] = scoresItem;
        }

        int aliceCount = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[] alice = new int[aliceCount];

        String[] aliceItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < aliceCount; i++) {
            int aliceItem = Integer.parseInt(aliceItems[i]);
            alice[i] = aliceItem;
        }

        int[] result = climbingLeaderboard(scores, alice);

        for (int i = 0; i < result.length; i++) {
            bufferedWriter.write(String.valueOf(result[i]));

            if (i != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}