[Algorithm] HackerRank : Climbing the Leaderboard

HackerRank Medium: Climbing the Leaderboard

코드

import Foundation

func climbingLeaderboard(scores: [Int], alice: [Int]) -> [Int] {
    var answer = [Int]()
    var sortedScores = [Int]()
    
    scores.forEach {
        if sortedScores.count == 0 {
            sortedScores.append($0)
        } else {
            if sortedScores[sortedScores.count - 1] != $0 {
                sortedScores.append($0)
            }
        }
    }
    
    var aliceIndex = 0
    var scoreIndex = sortedScores.count - 1
    
    while aliceIndex < alice.count {
        if alice[aliceIndex] < sortedScores[scoreIndex] {
            aliceIndex += 1
            answer.append(scoreIndex + 2)
        } else if alice[aliceIndex] == sortedScores[scoreIndex] || scoreIndex == 0 {
            aliceIndex += 1
            answer.append(scoreIndex + 1)
        } else {
            scoreIndex -= 1
        }
    }
    
    return answer
}

문제 설명

leaderboard에 등록된 score들의 배열 scores가 내림차순으로 주어지고, alice의 점수들의 배열 alice가 오름차순으로 주어진다.
Dense Ranking을 적용하여 순위를 정한다.
(ex: [100, 90, 90, 80, 70] 배열이 주어 졌을 때, 등수는 각각 [1, 2, 2, 3, 4] 이다)
이 때 alice의 각 점수 순위를 반환하면 된다.

풀이 과정

먼저 scores 배열에서 중복을 없앤 sortedScores 배열을 만들었다. Set을 사용해서 중복을 없애도 되지만, 순서가 뒤죽박죽이 되기 때문에 다시 소팅해야한다는 점 때문에 바로 sortedScores 배열을 만들었다.

핵심 로직은 다음과 같다.
alice의 점수는 오름차순이고, scores 배열은 내림차순이다. 즉 현재 alice 점수의 등수는 이전 alice 점수의 등수보다 무조건 높거나 같기 때문에 현재 alice 점수보다 낮은 scores 배열의 값을 고려할 필요가 없다.

자세한 구현은 다음과 같다.

scoreIndex는 sortedScores 배열의 맨 마지막 인덱스이다.

alice 배열을 순회한다. 등수를 판단하는 로직은 3가지 경우로 나뉜다.

• alice의 점수가 현재 scores 배열의 값보다 작다.
  • alice의 다음 점수로 넘어가기 위해 aliceIndex += 1을 해주고, 현재 점수보다 작기 때문에 다음 등수로 밀려나야함. 따라서 scoreIndex + 2을 result 배열에 넣어준다.
• alice의 점수가 현재 scores 배열의 값과 같다.
  • alice의 다음 점수로 넘어가기 위해 aliceIndex += 1을 해주고, 점수가 같으면 다음 등수로 밀려나지 않기 때문에 scoreIndex + 1을 result 배열에 넣어준다.
• rank가 0이다.
  • alice의 점수가 최고점이므로 result 배열에 1을 넣어준다.
• alice의 점수가 현재 scores 배열의 값보다 크다.
  • 현재 scores 배열의 값보다 크기 때문에 scores 배열의 다음 값과 비교하기 위해 scoreIndex -= 1 해준다.