[해커랭크] Climbing the Leaderboard

[해커랭크] Climbing the Leaderboard

https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem?isFullScreen=true

Climbing the Leaderboard | HackerRank

 

 

An arcade game player wants to climb to the top of the leaderboard and track their 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.

Example

The ranked players will have ranks , , , and , respectively. If the player's scores are ,  and , their rankings after each game are ,  and . Return .

Function Description

Complete the climbingLeaderboard function in the editor below.

climbingLeaderboard has the following parameter(s):

• int ranked[n]: the leaderboard scores
• int player[m]: the player's scores

Returns

• int[m]: the player's rank after each new score

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, , the number games the player plays.
The last line contains  space-separated integers , the game scores.

Constraints

•  
•  
•  for 
•  for 
• The existing leaderboard, , is in descending order.
• The player's scores, , are in ascending order.

Subtask

For  of the maximum score:

•  
•  

Sample Input 1

CopyDownload

Array: ranked1001005040402010 Array: player52550120

7
100 100 50 40 40 20 10
4
5 25 50 120

Sample Output 1

6
4
2
1

Explanation 1

Alice starts playing with  players already on the leaderboard, which looks like this:

After Alice finishes game , her score is  and her ranking is :

After Alice finishes game , her score is  and her ranking is :

After Alice finishes game , her score is  and her ranking is tied with Caroline at :

After Alice finishes game , her score is  and her ranking is :

Sample Input 2

CopyDownload

Array: ranked1009090807560 Array: player50657790102

6
100 90 90 80 75 60
5
50 65 77 90 102

Sample Output 2

6
5
4
2
1

 

 

 

 

 

 

풀이

코드를 보면 알다시피, 처음엔 그냥 Set에 중복없이 넣고, 정렬해서 List저장하고 index 찾으면 되겠구나 싶었다.

그 코드가 바로 climbingLeaderboardTimeout

타임아웃이 나더라

 

매번 정렬해주는게 문제일테고

문제상 ranked가 내림차순, palyer가 오름차순 정렬되어 input값으로 들어온다는 정보에 주목했다.

 

그리하여 푼 해결방법이 climbingLeaderboard 이다.

while문으로 player의 첫번째 큰 숫자값부터 하나를 꺼내서,

ranked의 가장 우측에서부터 몇등인지 체크하는 방식으로 풀어냈다.

 

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

class Result {

    /*

     * Complete the 'climbingLeaderboard' function below.

     *

     * The function is expected to return an INTEGER_ARRAY.

     * The function accepts following parameters:

     *  1. INTEGER_ARRAY ranked

     *  2. INTEGER_ARRAY player

     */

    public static List<Integer> climbingLeaderboardTimeout(List<Integer> ranked, List<Integer> player)throws IOException {

    // Write your code here

   

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

        for(Integer p : player){

            ranked.add(p);

            Set<Integer> uniqueSet = new HashSet<>(ranked);

            List<Integer> uniqueList = new ArrayList<>(uniqueSet);

            Collections.sort(uniqueList, Collections.reverseOrder());

            dap.add(uniqueList.indexOf(p)+1);

        }

        return dap;

    }

   

    public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player)throws IOException {

        Set<Integer> uniqueSet = new HashSet<>(ranked);

        List<Integer> uniqueList = new ArrayList<>(uniqueSet);

        Collections.sort(uniqueList, Collections.reverseOrder());

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

        int index = uniqueList.size();  // start from minimum number (=last index)

        for (Integer p : player) {

            while (index >= 0 && p >= uniqueList.get(index)) {

                index--;

            }

           

            // index = 4

            // player = 30

            // 100 50 40 20 10

            // index=2 -> rank=4

            dap.add(index + 2);

        }

        return dap;

    }

}

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int rankedCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> ranked = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))

            .map(Integer::parseInt)

            .collect(toList());

        int playerCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> player = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))

            .map(Integer::parseInt)

            .collect(toList());

        List<Integer> result = Result.climbingLeaderboard(ranked, player);

        bufferedWriter.write(

            result.stream()

                .map(Object::toString)

                .collect(joining("\n"))

            + "\n"

        );

        bufferedReader.close();

        bufferedWriter.close();

    }

}