[Hacker Rank, 해커랭크] Climbing the Leaderboard 문제 및 풀이( C# )

문제 링크: https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem#!

Climbing the Leaderboard | HackerRank

 

안녕하세요, 이번 HackerRank 문제는 랭킹보드에서 자신의 점수들이 몇등에 해당하는지 찾아내면 되는 문제입니다.
보기엔 간단해보였지만 주먹구구식으로 풀었다간 쉽게 Timeout이 걸려버리는 마법에 걸립니다..;

문제 요약

난이도: Medium

• Dense Ranking의 방식인 순위표가 있고, 그 순위표엔 여러 점수들이 들어가 있습니다.
• 앨리스의 점수들을 이 순위표에 대입했을때, 각각의 점수들은 과연 몇등을 하는지 찾으면 됩니다.

Example

100

100

50

40

40

20

10

Array: 순위표의 점수 배열

5

25

50

120

Array: 앨리스의 점수 배열

------------------------

결과 -> 6 4 2 1 ( 각각의 등수를 출력하면 됨 )

---

문제 풀이

처음에는 앨리스 점수를 일일이 랭킹 점수들과 비교하면서 문제를 풀려고 하였습니다.
그러나 점수배열의 크기와 앨리스의 점수 갯수가 많아지면서 시간은 O(n)^2로 올라가게 되었고,
결국 Time out에 걸려버리고 말았습니다.

그래서 어떻게하면 검색 횟수를 줄일 수 있을지 곰곰히 생각해본 결과, 이진탐색이 떠올랐습니다.

이진탐색을 사용하기 위해 우선 이 문제를 두 부분으로 나눴습니다.

1. Scores 배열을 바탕으로 등수 정보를 가진 배열 생성

2. 앨리스의 점수들을 Binary Search를 통해 Score 배열의 index를 알아내고,
그 index를 1번에서 만든 등수정보 배열에 넣어 그대로 등수 반환

---

2번에서 한가지 예외가 발생하게 되는데,
만약 제일 마지막 index의 점수보다 앨리스의 점수가 더 작을 경우,
마지막 index의 등수에 +1을 해주시면 됩니다.

마지막으로 실제 구현 코드를 올리면서 마치겠습니다~!

궁금한 사항이 있으시면 언제든지 댓글로 남겨주시기 바랍니다!
감사합니다:)

using System;

class Solution
{
    static int[] ClimbingLeaderboard(int[] scores, int[] aliceScores)
    {
        return GetAliceRanksByBinarySearch(scores, aliceScores, CreateRankArray(scores));
    }

    private static int[] CreateRankArray(int[] scores)
    {
        var scoreRankArr = new int[scores.Length];
        var curRank = 1;
        for (var i = 0; i < scoreRankArr.Length; ++i)
        {
            scoreRankArr[i] = curRank;

            if (i >= scores.Length - 1 || scores[i] != scores[i + 1])
                ++curRank;
        }
        return scoreRankArr;
    }

    private static int[] GetAliceRanksByBinarySearch(int[] scores, int[] aliceScores, int[] scoreRanks)
    {
        var aliceRanks = new int[aliceScores.Length];

        for (var i = 0; i < aliceScores.Length; ++i)
        {
            var curAliceScore = aliceScores[i];
            var left = 0;
            var right = scores.Length - 1;
            var mid = 0;

            while (right >= left)
            {
                mid = (left + right) / 2;

                if (curAliceScore > scores[mid])
                    right = mid - 1;
                else
                    left = mid + 1;

                if (curAliceScore == scores[mid])
                    break;
            }

            if (curAliceScore < scores[mid])
                aliceRanks[i] = scoreRanks[mid] + 1;
            else
                aliceRanks[i] = scoreRanks[mid];
        }

        return aliceRanks;
    }

    static void Main(string[] args)
    {
        int scoresCount = Convert.ToInt32(Console.ReadLine());
        int[] scores = Array.ConvertAll(Console.ReadLine().Split(' '), scoresTemp => Convert.ToInt32(scoresTemp));
        int aliceCount = Convert.ToInt32(Console.ReadLine());
        int[] alice = Array.ConvertAll(Console.ReadLine().Split(' '), aliceTemp => Convert.ToInt32(aliceTemp));
        int[] result = ClimbingLeaderboard(scores, alice);

        Console.WriteLine(string.Join("\n", result));
    }
}