[HackerRank] Climbing the Leaderboard (JAVA - binarySearch, stream)

binaySearch

Arrays.binarySearch() 메서드는 이진 탐색 알고리즘을 이용하여 정렬된 배열에서 특정 값을 찾는 메서드이다. 

Collenctions.binarySearch() 메서드를 이용해 리스트에서도 이진 탐색이 가능하다.

 

JAVA 공식문서

 

이진 탐색은 시간 복잡도는 평균 및 최악의 경우에도 O(log N)이기 때문에 알고리즘 문제에서 효율성을 고려할 때 많이 사용되는 탐색 기법이다.

 

int[] arr = new int[]{10, 20, 30, 40, 50};

int idx1 = Arrays.binarySearch(arr, 1); // -1
int idx20 = Arrays.binarySearch(arr, 20); // 1
int idx25 = Arrays.binarySearch(arr, 25); // -3

// 리스트 (결과는 위와 같음)
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
idx1 = Collections.binarySearch(list, 1);
idx20 = Collections.binarySearch(list, 20);
idx25 = Collections.binarySearch(list, 25);

 

 

배열에서 찾고자 하는 key가 존재하지 않는다면, - (배열에 삽입 시 들어가게 될 인덱스 + 1) 을 리턴하고, 배열에 찾으려는 key가 존재한다면, 해당 인덱스를 리턴한다. 

 

위 예시에서 보면 1은 배열에 없는 값이며 가장 작기 때문에 - ( 0 + 1 ) = -1을 리턴

20은 배열 2번째에 위치한 값으로 인덱스인 1 리턴

25는 배열 20과 30 사이에 삽입이 가능하기 때문에 - ( 2 + 1 ) = -3을 리턴

 

🔒 HackerRank - Climbing the Leaderboard

문제 링크

 

문제 설명

예시)

ranked, player 두 배열이 주어진다.

ranked = [100, 90, 90, 80]

player = [70, 80, 105]

 

ranked는 이미 존재하는 점수고 순위는 각각 1, 2, 2, 3위이다. (중복이 있어도 다음 순위는 +1위이다)

player는 각 게임의 점수고 매 게임이 끝날 때마다 순위를 매긴다.

70점은 (100, 90, 90, 80, 70) 중 4위, 80점은 (100, 90, 90, 80, 80, 70) 중 3위, 105점은 (105, 100, 90, 90, 80, 80, 70) 중 1위가 되므로 [4, 3, 1]을 리턴한다.

🔑 문제 풀이

public static List<Integer> climbingLeaderboard(List<Integer> ranked, List<Integer> player) {
    ranked = ranked.stream().distinct().sorted().collect(toList()); // 1
    List<Integer> ans = new ArrayList<>(); 
    for (Integer score : player) {
        int idx =  Collections.binarySearch(ranked, score); // 2
        if(idx < 0){ // 3
            ranked.add(-idx - 1, score); // 3-1
            ans.add(ranked.size() + idx + 1); // 3-2
        }else{ // 4
            ans.add(ranked.size() - idx);
        }
    }
   return ans;
}

 

1. ranked에서 중복 제거 후 정렬

 

2. 이진 탐색으로 ranked 리스트에서 player의 스코어를 탐색 

 

3. player의 스코어가 ranked 리스트 존재하지 않는 경우 (binarySearch()메서드가 음수를 리턴)

3-1 idx =  - (배열에 삽입 시 들어가게 될 인덱스 + 1) 이므로 스코어를 추가할 인덱스는 - idx -1이 된다.

3-2 ranked는 오름차순으로 정렬되었기 때문에 순위는 (ranked 리스트 사이즈 - ranked에 추가된 score의 인덱스) 

 

4. player의 스코어가 ranked 리스트에 존재하는 경우 정답 리스트에 (ranked 리스트 사이즈 - 해당 인덱스(idx)) 만 추가하면 된다.