Climbing the Leaderboard javascript 번역 및 풀이

원문

Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:

• The player with the highest score is ranked number 1 on the leaderboard.
• Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.

For example, the four players on the leaderboard have high scores of 100, 90, 90, and 80. Those players will have ranks 1, 2, 2, and 3, respectively. If Alice's scores are 70,80  and 105, her rankings after each game are 4^th, 3^th  and 1^st.

 

 

Function Description

Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element res[j] represents Alice's rank after the j^th game.

climbingLeaderboard has the following parameter(s):

• scores: an array of integers that represent leaderboard scores
• alice: an array of integers that represent Alice's scores

 

번역

앨리스는 아케이드 게임을 하고있으며 리더보드에 탑으로 올라가는 것과 그녀의 랭킹을 추적하길 원한다.

게임은 Dense Ranking을 사용하고, 리더보드는 다음과 같이 동작한다.

-> 플레이어 중 가장 높은 점수가 1번이 되는 리더보드이다.

-> 플레이어가 동일한 점수이면, 동일한 랭킹 넘버를 받으며, 다음 플레이어는 바로 다음 랭킹 번호를 받는다.

예를들어 플레이어 4명의 점수가 각각 100, 90, 90, 80이면, 플레이어는 각각 1,2,2,3 의 랭킹을 가진다. 만약 엘리스의 스코어가 70, 80, 105라면 그녀의 랭킹은 각각 4등, 3등, 1등이다.

 

함수 설명

아래 에디터에서 climbingLeaderboard 함수를 완성하라. 리턴값은 앨리스의 j번째 게임 순위를 각각의 원소로 하는 정수형 배열을 나타낸다.

climbingLeaderboard 함수는 아래와 같은 파라미터를 받는다.[s]

스코어 : 정수형 배열로 리더보드의 스코어를 나타낸다.

앨리스 : 정수형 배열로 앨리스의 점수를 나타낸다.

 

 

문제풀이

자바스크립트라서 sort, reduce를 사용하면 쉽게 해결할 수 있을 것 같다.

다만 로직은 쬐끔 복잡하다.

1. 앨리스의 스코어 배열을 순회하면서
2. 앨리스의 점수를 리더보드에 푸쉬한뒤
3. 정렬한다음에(sort)
4. 중복값 제거를 한다.(reduce)
5. indexOf로 몇번째인지 출력한다.

--

 

인줄 알았는데

자바스크립트에서 중복값을 제거하는 로직이 매우 효율이 구린 문제가 있었다.

정확하게 말하면 reduce 함수로직의 효율이 좋지 않다.

일일히 값을 indexOf로 찾는것도 해봤지만 이것 역시 효율이 좋지 않다.

결국은 이진트리를 써서 해결해야하는 것으로 보인다.

 

그런데 이진트리로 해도 틀렸다고 나온다.

아예 접근 방법이 틀렸나보다

(참고로 다른 언어로 푼 사람들은 문제 없이 잘 넘어갔음)

 

생각해보니 리더보드는 무조건 내림차순, 엘리스의 점수는 무조건 오름차순으로 들어온다.

즉 리더보드의 뒤부터 탐색하면 이진트리보다 효율이 더 나온다.

따라서 해결방법은 이렇다.

 

중복된 값을 제거한 리더보드를 맨 뒤부터 탐색하면서

  1. 찾는 값이 있으면 현재 위치 를 추가

  2. 찾는 값보다 현재 위치의 값이 더 크면 현재 위치의 +1을 추가

  3. 리더보드를 전부 순회하면서 이미 1위에 도달했다면 무조건 1

이렇게 처리하면 된다.

참고로 중복된 값을 제거하는 방법은 reduce를 쓰면 안된다. 겁나게 느리다.

set을 이용하도록 하자.

 

자바스크립트 소스코드

    climbingLeaderboard : function (scores, alice) {
        // var set = new Set(scores);
        // scores = Array.from(set);
        scores = Array.from(new Set(scores));
        var res = [];
        var searchKey = scores.length-1
        for(var i=0;i<alice.length;i++){
            for(var j=searchKey;j>=0;j--){
                if(alice[i]==scores[j]){
                    res.push(j+1);
                    searchKey = j;
                    break;
                }else if(alice[i]<scores[j]){
                    res.push(j+2);
                    searchKey = j;
                    break;
                }else if(j==0){
                    res.push(1);
                }
            }
        }
        return res;
    }

 

참고로 이상하게 해커랭크에서 채점을 하면 틀리다고 나오는 답이 몇개 있다.

해당 답은 직접 내려받아 비교해봤는데 문제가 없더라.

혹시나 해서 첨부해둔다.

정답.xlsx

3.71MB