[이진탐색 구현] Climbing the Leaderboard

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

Climbing the Leaderboard | HackerRank

분류: Problem Solving (Basic)

 

문제 내용

"중복 순위가 있는 랭킹 시스템에서 새 점수의 순위를 계산" 하는 문제

 

🧩 문제 설명

📘 상황

• 기존 플레이어들의 점수가 있음: ranked = [100, 100, 50, 40, 40, 20, 10]
• 새로운 플레이어 Alice가 게임을 하면서 점수를 획득함: player = [5, 25, 50, 120]

기존 점수는 내림차순이며, 같은 점수는 같은 등수를 가짐.

 

🎯 목표

각 Alice의 점수마다, 기존 ranked에 넣었을 때 몇 등인지를 출력하라.

 

✅ 문제 포인트

• 중복 점수는 하나로 취급해야 함 → 순위표는 unique
• 입력 순서대로 결과를 출력해야 함
• 최적화 필요: ranked 최대 200,000, player 최대 10,000 → 단순 for문은 시간 초과 💥

 

🔑 해결 전략

1. 중복 제거 + 내림차순 정렬 → 순위표 uniqueRanked 만들기
2. 각 player 점수마다 uniqueRanked에서 이분 탐색으로 등수 계산

 

코드

    public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
        List<Integer> answer = new ArrayList<>();
        // 중복 제거
        List<Integer> filteredRank = ranked.stream()
                .distinct()
                .collect(Collectors.toList());
        // 이진 탐색을 위해 정렬
        Collections.sort(filteredRank, Comparator.reverseOrder());

		// 점수별로 순위 계산
        player.forEach(score -> {
            int rank = getRank(filteredRank, score);
            answer.add(rank);
        });

        return answer;
    }
    public static int getRank(List<Integer> ranked, int score) {
    	// 이진 탐색 초기화
        int start = 0;
        int end = ranked.size() - 1;

		
        while(start <= end) {
            int mid = (start + end) / 2;
            int midScore = ranked.get(mid);            
            
            if(score == midScore) { // 동일점수면 동일 등수
                return mid + 1;
            } else if (score < midScore) { // 점수가 더 낮으면 start 기준을 변경
                start = mid + 1;
            } else { //점수가 더 높으면 end 기준을 변경
                end = mid - 1;
            }
        }

		// 찾지못하면 1등 or 최하등. 둘 다 start + 1을 하면 결국 등수가 나옴. 
        return start + 1;
    }