Programmers.실패율

문제 설명

실패율은 다음과 같이 정의한다.

• 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N

게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때

실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

문제 풀이

나의 풀이

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {

    var failure: [Int: Float] = [:]
    var player: Int = stages.count

    for i in 1...N {
        let n = stages.filter { $0 == i }.count
        failure[i] = Float(n)/Float(player)
        player -= n
    }

    return failure.sorted(by: <).sorted(by: { $0.value > $1.value }).map {$0.key}
}

테스트 5, 테스트 9, 테스트 22에서 시간 초과가 발생한다.

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {

    var failStage: [Int: Int] = [:]
    for stage in stages {
        if !failStage.isEmpty && failStage.keys.contains(stage) {
            failStage[stage]! += 1
            continue
            }
        failStage[stage] = 1
    }

    var result: [(stage: Int, value: Double)] = []
    var successPeople: Int = stages.count
    for stage in 1...N {
        if !failStage.keys.contains(stage) {
            result.append((stage, 0))
             continue
             }
        result.append((stage, Double(failStage[stage]!) / Double(successPeople)))

        successPeople -= failStage[stage]!
    }
    
    result.sort { return $0.value == $1.value ? $0.stage < $1.stage : $0.value > $1.value }
    return result.map { $0.stage }

}

정상적으로 채점 완료

힘들었던 점

시간 복잡도를 따지지 않고 문제를 풀다보니

고차 함수가 느린 함수라는 점을 모르고 진행해서 시간초과가 난 점이다.

결국 인터넷에 다른사람의 블로그를 탐색하면서 틀린 이유를 찾았고 그 사람들의 코드를 보고 공부를 하면서 다시 코드를 짰다.

문제 바로가기