HackerRank Java Climbing the Leaderboard

문제풀기 : https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:
  • The player with the highest score is ranked number  on the leaderboard.
  • Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.
For example, the four players on the leaderboard have high scores of , and . Those players will have ranks , and , respectively. If Alice's scores are  and , her rankings after each game are  and .
Function Description
Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element represents Alice's rank after the  game.
climbingLeaderboard has the following parameter(s):
  • scores: an array of integers that represent leaderboard scores
  • alice: an array of integers that represent Alice's scores
Input Format
The first line contains an integer , the number of players on the leaderboard.
The next line contains  space-separated integers , the leaderboard scores in decreasing order.
The next line contains an integer, , denoting the number games Alice plays.
The last line contains  space-separated integers , the game scores.
Constraints
  •  for 
  •  for 
  • The existing leaderboard, , is in descending order.
  • Alice's scores, , are in ascending order.
Subtask
For  of the maximum score:
Output Format
Print  integers. The  integer should indicate Alice's rank after playing the  game.


첫 번째로 LeaderBoard를 배열로 입력받고
두 번째로 Alice의 점수들을 배열로 입력받는다.
그리고 Alice의 점수들이 LeaderBoard에서 몇등인지를 배열로 반환하는 함수를 작성하면 된다.

1. 첫 번째 시도 - 무식하게 다 확인하기 
12 test case중 4개 case에서 시간초과..!!
테스트 데이터가 LeaderBoard로 배열의 길이가 200,000!!
따라서 Alice 게임 점수가 5개만 하더라도 5 * 20,000 = 1,000,000
무려 100만 번이나 연산을 해야된다.
아래에는 첫 번째 소스코드.
static int[] climbingLeaderboard(int[] scores, int[] alice) {
    HashSet<Integer> hs = new HashSet<>();
    for (int i = 0; i < scores.length; i++){
        hs.add(scores[i]);
    }
    Integer[] arr = new Integer[hs.size()];
    arr = hs.toArray(arr);
    Arrays.sort(arr, Comparator.reverseOrder());

    int[] aliceRanks = new int[alice.length];
    for (int i = 0; i < alice.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            if(alice[i] > arr[j]) {
                aliceRanks[i] = j + 1;
                break;
            } else if (alice[i] == arr[j]) {
                aliceRanks[i] = j + 1;
                break;
            }
        }
        if (aliceRanks[i] == 0)
            aliceRanks[i] = arr.length+1;
    }
    for (int i : aliceRanks) {
        System.out.println(i);
    }
    return aliceRanks;
}

1. 두 번째 시도 - Binary Search
이번에는, 무식하게 일일히 n*m 연산하는 것말고 Alice의 점수의 위치를 찾아가면 어떨까 해서
생각난게 Binary Search 였다.
모든 테스트케이스 통과!
아래의 고친 코드를 보면 getRank()함수에서 Binary Search를 하고 있다.
static int[] climbingLeaderboard(int[] scores, int[] alice) {
    HashSet<Integer> hs = new HashSet<>();
    for (int i = 0; i < scores.length; i++){
        hs.add(scores[i]);
    }
    Integer[] arr = new Integer[hs.size()];
    arr = hs.toArray(arr);
    Arrays.sort(arr, Comparator.reverseOrder());

    int[] aliceRanks = new int[alice.length];
    for (int i = 0; i < alice.length; i++) {
        aliceRanks[i] = getRank(alice[i], arr, 0, arr.length);
        System.out.println(aliceRanks[i]);
    }
    return aliceRanks;
}

static int getRank(int aliceScore, Integer[] leaderBoard, int start, int end) {
    int half = (start + end)/2;
    if (start >= leaderBoard.length)
        return leaderBoard.length+1;
    if (end < start)
        return start+1;
    if (aliceScore > leaderBoard[half]) {
        return getRank(aliceScore, leaderBoard, start, half-1);
    } else if (aliceScore < leaderBoard[half]) {
        return getRank(aliceScore, leaderBoard, half+1, end);
    } else {
        return half+1;
    }
}



댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째