[swift] 프로그래머스 - 실패율

프로그래머스

---

문제풀이를 직관적으로 이해할 수 있도록 고차함수를 사용하지 않은 풀이와
고차함수를 사용한 풀이로 나누어 공부하고 있습니다.
- 문제에 따라 하나의 풀이만 있을 수 있습니다.

 

실패 풀이 1

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    var failureLate = [Int: Double]()

    for i in 1...N {
        let yet = stages.filter { $0 == i }.count
        let clear = stages.filter { $0 >= i }.count
        failureLate[i] = Double(yet) / Double(clear)
    }

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

 

후... 나의 첫번째 실패 풀이다

 

5,9,22번이었나 자꾸 시간초과가 나서 별의 별짓을 다 해봤다

Double을 Float으로 줄여보고 Float16 으로 줄여보고..

 

하쥐만 어림없는 똥볼^^

 

결과적으로는 for문 안에 있는 filter들이 문제였다.

그래서 나온 실패 풀이2

 

실패 풀이 2

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    var failureLate = [Int: Float32]()
    var count = stages.count
    for i in 1...N {
        let yet = stages.filter { $0 == i }.count
        failureLate[i] = Float32(yet) / Float32(count)
        count -= yet
    }
    return failureLate.sorted(by: <).sorted(by: { $0.value > $1.value }).map { $0.key }
}

 

filter를 하나 줄였다!!!

 

는 시간초과

그냥.. 안풀게요^^

 

라고하기엔 매몰된 시간이 너무 아깝다

 

바로 3번째 풀이

 

성공 풀이

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    var failureLate = [Int: Double]()
    var count = stages.count
    for i in 1...N {
        var yet = 0
        for j in 0..<stages.count {
            if stages[j] == i {
                yet += 1
            }
        }
        count -= yet
        failureLate[i] = Double(yet) / Double(count)
    }
    return failureLate.sorted(by: <).sorted(by: { $0.value > $1.value }).map { $0.key }
}

 

복잡도는~ for문을 좋아해~

어짜피 O(n)으로 똑같은거 아닌가..

 

stages의 길이 즉 사람인원수 만큼을 count 변수로 저장해 놓고

0부터 stages를 쫙 돌면서 현재 스테이지에 남아있는 사람 수(yet) 만큼 count에서 빼고

yet / count 해서 미리 만들어둔 딕셔너리에 쏙 쏙 넣는다

그 후 정렬은 위와 같음

 

이렇게 풀이성공을 했지만

여전히 찝찝하다

그래도 자료구조랑 시간복잡도에 대해 찾아보면서 공부해서

마냥 시간은 날린게 아니라 위로중..

이제는 시간복잡도도 생각하면서 알고리즘을 생각해보고 풀어보자!