[programmers/Swift] 실패율 (2019 Kakao Blind Recruitment)

programmers.co.kr - 코딩테스트연습 - Lv.1 - 2019 Kakao Blind Recruitment - 실패율

코딩테스트 연습 - 실패율

Constraints :

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/05/06.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

func solution(_ n: Int, _ stages: [Int]) -> [Int] {
    var tries = Array(repeating: 0, count: n + 1)

    for lastStage in stages {
        for stage in 0..<lastStage {
            tries[stage] += 1
        }
    }

    var result = [Int:Double]()
    for i in 0..<n {
        result.updateValue(Double(tries[i] - tries[i + 1]) / Double(tries[i]), forKey: i + 1)
    }

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

print(solution(5, [2, 1, 2, 6, 2, 4, 3, 3])) // [3,4,2,1,5]
print(solution(4, [4,4,4,4,4]))              // [4,1,2,3]

How I tried this :
첫 시도에서 무지성으로 풀다가 시간초과를 마주했다.

Stage가 5까지 있어도 6이란 숫자가 나온다는 점에서 index 접근이 떠올라서 

매번 체킹하는 형태보다 각 Stage에 오기까지 거친 Stage 

 

What I got is :

// 시간초과 나온 풀이
func solution(_ n: Int, _ stages: [Int]) -> [Int] {
    var rates = [Int:Double]()
    
    for stage in 1...n {
        let triedStageCount = stages.filter({ i<=$0 }).count
        let failedStageCount = stages.filter({ i==$0 }).count
 
        let rate = Double(failedStageCount)/Double(triedStageCount)
        rates.updateValue(rate, forKey: stage)
    }

    let result = rates.sorted(by: <).sorted(by: {$0.value > $1.value}).map({$0.key})
    
    return result
}

반드시 제약조건을 보고 시간초과에 대해 의식할 것

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다

조건을 대입했을 때 최악에 상황에서 stages * stages
최대치가 40,000,000,000 ... 굉장히 크다

 

 

문제에 관한 모든 저작권 : https://programmers.co.kr/