[HackerRank] Climbing the Leaderboard 자바

문제

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

Climbing the Leaderboard | HackerRank

풀이

#이진탐색

1. 중복 제거

동점자는 동일 순위로 치기 때문에 HashSet을 이용하여 중복을 제거해줬다.

2. 이진탐색

처음에 그냥 구현으로 풀었었는데 틀려서 이진탐색을 이용해서 풀었다.

앨리스의 점수가 원래 있던 ranked 배열의 점수의 범위를 넘어가는 경우가 있다. 1등보다 점수가 더 높은 경우와 꼴등보다 점수가 더 낮은 경우가 있는데, 1등보다 점수가 더 높은 경우는 점수가 더 높더라도 똑같이 1등이 되지만 꼴등보다 점수가 더 낮은 경우에는 꼴등보다 +1등이기 때문에 마지막에 예외처리를 해준다. (안해주면 테스트케이스2번에서 틀림!)

 

코드

package HackerRank.medium;
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> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
        HashSet<Integer> set=new HashSet<>(ranked);
        ranked=new ArrayList<>(set);
        Collections.sort(ranked, Collections.reverseOrder());


        List<Integer> answer=new ArrayList<>();
        for(int score: ranked){
            System.out.println(score);
        }

        for(int p:player){

            int left=0; //1
            int right=ranked.size()-1; //last
            int mid=0;

            int rank=0;
            while(left<=right){
                mid=(left+right)/2;
                if(p>ranked.get(mid)){
                    right=mid-1;
                }else{
                    left=mid+1;
                }

                if(p==ranked.get(mid)) break;
            }

            if(p<ranked.get(mid)){
                rank=mid+1;
            }else{
                rank=mid;
            }
            answer.add(rank+1);
        }


        for(int ans:answer){
            System.out.println(ans);
        }
        return answer;
    }

}