[HackerRank] Climbing the Leaderboard - Csharp

ranked는 내림차순, player는 오름차순이니까 이진탐색을 사용하면 된다고 생각했다.

 

근데 둘중 한 리스트를 뒤집어서 효율적으로 순회하는 방법으로 풀었다.

(그리고 왠지 Dictionary가 쓰고싶었다).

 

public static List<int> climbingLeaderboard(List<int> ranked, List<int> player)

    {  

        var result = new List<int>();

       

        //initialize Dictionary

        var playerScoreDictionary = new Dictionary<int, int>();

        player.Reverse();

        foreach(var scoreValue in player)

        {

            if( playerScoreDictionary .ContainsKey(scoreValue)) playerScoreDictionary [scoreValue]++;

            else

            {

                playerScoreDictionary .Add(scoreValue, 1);

            }

        }

       

        //search

        var rankIndex = 1;

        var rankedDistinct = ranked.Distinct().ToList();

       

        foreach(var score in playerScoreDictionary )

        {

            for(int j = rankIndex; j <= rankedDistinct.Count; j++)

            {

                if(score.Key >= rankedDistinct[rankIndex - 1]) break;

                else

                {

                    rankIndex++;

                }

            }

           

            for(int i = 0; i < score.Value; i++)

            {

                result.Add(rankIndex);

            }

           

        }

       

        result.Reverse();

        return result;

    }

간단하게 구조를 설명하자면,

1. playerScoreDictionary에 플레이어 점수 정보(player)를 Reverse()한 뒤 재구성한다. 연속되는 정보를 묶기 위함 & ranked와 정렬을 맞추기 위함이다.

2. ranked에서 중복되는 점수정보를 제거하는 rankedDistinct 리스트를 선언한다.

2. playerScoreDictionary의 원소를 하나씩 순회하기 위해 foreach문을 돌린다. (Dictionary를 만들어놓고 처음부터 순회하는게 마음이 불편하긴 하다)

3. foreach문 안에서 돌아가는, rankedDistinct를 순회하는 for문은 매번 처음부터 순회하지 않도록 외부에서 index를 관리한다. 이렇게 할 수 있는 이유는 플레이어의 점수 정보는 순차적으로 정렬되어있기 때문에 이미 지나간 점수 구간이라면 다시 탐색할 이유가 없기 때문이다.

4. for문에서 알맞은 구간을 찾았다면 break되어 아래의 for문으로 이동한다. 여기서는 플레이어가 현재의 점수를 몇번 맞았는지 확인하고, 그만큼 rank정보를 result에 쌓아준다.

5. foreach문이 종료되었을때, 랭크 정보는 역순으로 기록되어있기 때문에(player의 점수를 처음에 Reverse()했기 때문) 다시 Reverse()를 시켜준다.

 

 

풀긴 했는데 너무 야매같다. 이진탐색으로 다시 풀어야겠다.