[Swift] 프로그래머스 LV1 실패율(시간 초과 해결)

프로그래머스 LV1 실패율(시간 초과 해결)

 

✅ 우선 5번이랑 9번이 시간 문제로 통과가 안되었다.

그래서 나는 코드를 개선해야함을 느꼈는데 방법은 크게 두 가지가 있다.

 

✅ 1. dictionary -> tuple로 변경

✅ 2. filter -> for문으로 변경

 

이 두개를 통해 해결했다. 

 

결론 : 코딩 테스트에서는 튜플 적극 활용하고 filter보다는 for문을 더 사용해보자.

 

 

아.. 시간 초과로 통과가 안된다.

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
        var dict = [Int: Double]() // [스테이지: 실패율]
        var player = stages.count
        
        for i in 1...N {
            let current = stages.filter { $0 == i }.count // 현재 스테이지에 머무른 사람 수
            let divisor = stages.filter { $0 >= i }.count // 현재 스테이지 이상의 사람 수
            player -= current
            
            // 딕셔너리로 묶어서 담자
            dict[i] = Double(current) / Double(divisor)
        }

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

내 코드인데 개선해보자.

 

 

문제를 해결하려고 찾아보다가 다른 사람의 dictionary가 아니라 tuple로 작성한 코드가 있었는데 이 분의 코드대로 나도 수정!!

 

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
        var tuple = [(Int, Double)]() // [스테이지: 실패율]
        var player = stages.count
        
        for i in 1...N {
            let current = stages.filter { $0 == i }.count // 현재 스테이지에 머무른 사람 수
            player -= current
            
            // 딕셔너리로 묶어서 담자
            let ratio = Double(current) / Double(player)
            tuple.append((i, ratio))
        }
        print(tuple)

        tuple = tuple.sorted(by: {$0.1 > $1.1 })
        
        return tuple.map{ $0.0 }
    }

이렇게 작성하니까 통과는 했는데, 시간을 한번 보자면

걸린 시간

 

위와 같은 사진의 시간을 보여주게 된다.

일단 시간 초과는 5번이랑 9번이 주로 났었는데, 그래서 이번엔 filter가 문제라고 생각해서 코드를 조금 더 개선해 보았다.

 

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
        var tuple = [(Int, Double)]() // [스테이지: 실패율]
        var player = stages.count
        
        for i in 1...N {
            var current = 0
            for j in 0..<stages.count {
                if stages[j] == i {
                    current += 1
                }
            }
            
            player -= current
            
            // 딕셔너리로 묶어서 담자
            var ratio = Double(current) / Double(player)
            tuple.append((i, ratio))
        }
        print(tuple)

        tuple = tuple.sorted(by: {$0.1 > $1.1 })
        
        return tuple.map{ $0.0 }
    }

filter -> for문으로 코드를 변경하였을 때의 걸리는 시간이다.

 

시간이 엄청나게 줄어든 것을 확인할 수 있다!! 

 

 

 

filter의 시간 복잡도가 O(N)으로 알고 있는데, for이 훨씬 빠르다니..!

filter가 아닌 for문을 코딩 테스트에서 적극 활용해야 겠다.

 

 

 

(참고) 아래 분 글에서 실마리를 얻었습니다:)

https://42kchoi.tistory.com/335

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