문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

아케이드 게임 플레이어는 리더보드의 정상에 오르는 것과 그들의 순위를 추적하는 것을 원한다. 게임은 dense Ranking을 사용하고, 리더보드는 아래의 방법으로 작동한다.

• 가장 높은 점수를 가진 플레이어는 리더보드에서 숫자 1에 위치한다.
• 동점인 선수들은 동일한 순위를 받고, 다음 선수는 바로 다음 순위를 받는다.

Example

ranked = [100, 90, 90, 80]
player = [70, 80, 105]

순위에 오른 플레이어는 각각 순위 1, 2, 2, 3을 가지게 될 것이다. 만약 플레이어들의 점수가 70, 80, 105 라면 그들의 순위는 이후 각각 게임에서 4, 3, 1이다. [4, 3, 1]을 반환한다.

Function Description

climbingLeaderboard 함수를 완성해라.
climbingLeaderboard 함수는 아래와 같은 매개변수를 가지고 있다.

• int ranked[n]: 리더보드의 점수
• int player[m]: 플레이어의 점수

Return

• int[m]: 이후 각각 새로운 점수의 플레이어의 순위

Constraints

• 1 <= n <= 2 * 10^5
• 1 <= m <= 2 * 10^5
• 0 <= ranked[i] <= 10^9 (0 <= i < n)
• 0 <= player[j] <= 10^9 (0 <= j < m)
• 존재하는 리더보드인 ranked는 내림차순이다.
• 플레이어들의 점수인 player는 오름차순이다.

Solved

이중 반복문과 투 포인트를 사용한다면 타입리미트에 걸리게 된다. 그래서 이분탐색을 사용했다.

먼저 이분탐색을 할 수 있게 메소드를 만든다.

public static int search(List<Integer> ranked, int player) {
	int low = 0;
	int high = ranked.size() - 1;

	while (low <= high) {
		int mid = (low + high) / 2;

		if (ranked.get(mid) == player){
			return mid;
		}else if (ranked.get(mid) < player){
			high = mid - 1;
		}else{
			low = mid + 1;
		}
	}

	return low;
}

이제 결과를 반환한 메소드를 완성한다. Dense Ranking은 동일한 값이면 중복된 순위를 부여하기 때문에 주어진 ranked에서 중복값을 제거한다. 이후 리스트 player를 반복하여 순위를 지정하고 반환하면 된다.

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

	List<Integer> result = new ArrayList<>();
	ranked = ranked.stream().distinct().collect(Collectors.toList());

	for (int play : player) {
		int index = search(ranked, play);
		result.add(index + 1);
	}

	return result;
}

All Code

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

	List<Integer> result = new ArrayList<>();
	ranked = ranked.stream().distinct().collect(Collectors.toList());

	for (int play : player) {
		int index = search(ranked, play);
		result.add(index + 1);
	}

	return result;
}

public static int search(List<Integer> ranked, int player) {
	int low = 0;
	int high = ranked.size() - 1;

	while (low <= high) {
		int mid = (low + high) / 2;

		if (ranked.get(mid) == player){
			return mid;
		}else if (ranked.get(mid) < player){
			high = mid - 1;
		}else{
			low = mid + 1;
		}
	}

	return low;
}