[HakerRank] Climbing the Leaderboard

링크에 들어가서 보면 알겠지만 문제 자체는 쉽지만 시간 복잡도를 생각하지 않으면 시간복잡도를 만족시키기 어려운 문제이다.

우선 시간복잡도를 생각하지 않고 정말 단순하게 푸는 방법을 다음과 같이 생각하였다.

public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
    // Write your code here
        List<Integer> answer = new ArrayList<>();

        for(Integer playerScore : player) {
            var resultList = ranked.stream().distinct().filter(x -> x > playerScore).collect(Collectors.toList());
            answer.add(resultList.size() + 1);
        }
        
        return answer;
    }

이렇게 풀게되면 ranked와 player의 리스트 크기가 각가 N과 M이라 할때 O(N*M)의 시간 복잡도를 나타내게 된다.

각 값의 범위가 0~10^9 이기 때문에 당연히 시간 초과가 나온다.

 

따라서, TreeSet 자료구조의 특성을 이용하여 문제를 푼다.

    public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
        // Write your code here
        List<Integer> answer = new ArrayList<>();

        TreeSet<Integer> set = new TreeSet<>(ranked);

        Map<Integer, Integer> scoreMap = makeScoredMap(set);

        for(Integer playerScore : player) {
            answer.add(getPlayerRank(set, scoreMap,  playerScore));
        }

        return answer;
    }

    public static Map<Integer, Integer> makeScoredMap(TreeSet<Integer> set) {
    	//index를 Map에 저장해주기 위한 값이며 배열에 저장되야 하는 이유는 아래서 사용하는 스트림 때문인데 이 부분은 추후 자바 스트림 관련 게시물에서 작성하겠다.
        final int[] index = {set.size()}; 

        return set.stream().collect(Collectors.toMap(x -> x, x-> index[0]--));
    }

    public static Integer getPlayerRank(TreeSet<Integer> rankedSet, Map<Integer, Integer> scoredMap, Integer playerScore) {
        Integer ceilingScore = rankedSet.ceiling(playerScore);
        Integer floorScore = rankedSet.floor(playerScore);

        if(ceilingScore == null) return 1;

        if(ceilingScore.equals(floorScore)) return scoredMap.get(ceilingScore);
        else return scoredMap.get(ceilingScore) + 1;
    }

TreeSet은 순서 정렬이 보장된 Set으로 삽입 순서를 보장하지는 않지만 값에 대한 정렬을 유지한다.

(Set이기 때문에 당연히 중복은 허용하지 않는다.)

Binary Search Tree로 구현되어있기 때문에 범위 검색에서 높은 성능을 가진다.

 

이 코드의 핵심적인 부분은 바로 getPlayerRank 부분이다.

사전에 주어진 score의 Rank가 몇 등인지를 사전에 HashMap에 저장한다.

 

그 후 유저의 점수가 들어온다면 사전에 TreeSet에  존재하는 값 중 "같거나 가장 가깝지만 큰 값의 순서 + 1" 을 해주면 해당 유저의 Rank가 나온다.

public static Integer getPlayerRank(TreeSet<Integer> rankedSet, Map<Integer, Integer> scoredMap, Integer playerScore) {
    Integer ceilingScore = rankedSet.ceiling(playerScore);
    Integer floorScore = rankedSet.floor(playerScore);

    if(ceilingScore == null) return 1;

    if(ceilingScore.equals(floorScore)) return scoredMap.get(ceilingScore);
    else return scoredMap.get(ceilingScore) + 1;
}

ceiling과 floor 함수의 경우 TreeSet의 특징 덕분에 O(logN)의 시간 복잡도를 가지기 때문에 시간 복잡도를 만족시킬 수 있다.

 

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

Climbing the Leaderboard | HackerRank