[HackerRank] Climbing the Leaderboard (Medium) by javascript

▷ 문제 : Climbing the Leaderboard (Medium)

Climbing the Leaderboard | HackerRank

▷ 해결 날짜 : 2022.04.19
▷ 소요 시간 : 50분
▷ 풀이 과정 :
이번 문제는 플레이어가 점수를 갱신할 때 마다 변경된 랭크를 반환해 주는 문제이다.

ranked = [100, 90, 90, 80] , player = [70, 80, 105] 를 입력 받았을 때 결과값으로는 [4, 3, 1]을 반환해줘야 한다.

 

우선 여기서 까다로운점은 공동 순위가 존재해 저 ranked 의 순위는 [1, 2, 2, 3] 이다.

처음에는 그냥 하나하나 if문으로 걸러서 문제를 해결할라다가 뭔가 이진탐색으로 해결이 가능해보여서 이진탐색 알고리즘을 사용하였다.

 

우선 공동 순위가 있기때문에 의미가 없어 중복을 제거해주고 그 배열을 가지고 lowerBound 이진탐색을 진행하여 값을 찾아줘서 해결했다.

▷ 구현

function climbingLeaderboard(ranked, player) {
    const result = [];
    const newArr = [...new Set(ranked)];
    for(let score of player){
        result.push(lowerBound(newArr, score) + 1);
    }
    return result;
}

const lowerBound = (arr, target) => {
    let left = 0;
    let right = arr.length;
    while(left < right){
        const mid = Math.floor((left + right) / 2);
        if(arr[mid] <= target) right = mid;
        else left = mid + 1;
    }

    return left;
};

▷ 복기 :
문제를 이해하고 어떻게 풀지 고민하는 시간이 좀 길었던 문제이다.

아무래도 영문으로 되어있으니 더 시간이 걸리는 듯 하다...