[프로그래머스] 실패율 - Swift (Feat: 시간 초과)

2019 KAKAO BLIND RECUITMENT 문제이며, 난이도는 레벨 1입니다.

풀다가 시간 초과가 발생하게 되어서, 이중 for문 코드와, for문 안에 고차함수, 단일 for문 코드들을 모두 작성해 보았으며, 각각의 코드들의 시간을 측정해 보았습니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

이중 for문 코드

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    var stageCount = stages.count
    var dic = [Int:Double]()
    
    for stage in 1...N {
        var count = 0
        for i in stages {
            if stage == i {
                count += 1
            }
        }
        
        if count == 0 {
            dic[stage] = 0
        } else {
            dic[stage] = (Double(count)/Double(stageCount))
        }
        
        stageCount = stageCount-count
    }
    
    var resultArray = [Int]()
    
    resultArray = dic.sorted {
        if $0.1 == $1.1 {
            return $0.0 < $1.0
        }
        return $0.1 > $1.1
    }
    .map{$0.0}
    
    return resultArray
}

처음에 풀었던 이중 for문 로직입니다.
하지만 N으로 주어지는 범위가 1 이상 500이고, stages의 범위가 1부터 200,000이기 때문에, 이중 for문 코드를 작성시 testCase의 값이 많아질 때 시간 초과가 발생하게 됩니다.

 

for 문 안에 고차함수 코드

이번에는 이중 for문이 아닌 for문 안에 filter를 사용한 코드입니다.

    func solution(_ N:Int, _ stages:[Int]) -> [Int] {
        var stageCount = stages.count
        var dic = [Int:Double]()

        for stage in 1...N {
            
            let count = stages.filter{ $0 == stage }.count
            
            if count == 0 {
                dic[stage] = 0.0
            } else {
                dic[stage] = (Double(count)/Double(stageCount))
                stageCount -= count
            }
        }

        var resultArray = [Int]()

        resultArray = dic.sorted {
            if $0.1 == $1.1 {
                return $0.0 < $1.0
            }
            return $0.1 > $1.1
        }
        .map{$0.0}

        return resultArray
    }

 

 

각각의 코드들의 시간을 한번 측정해 보겠습니다.

일단 문제에서 주어지는 예제는 값이 작아 측정이 어렵기 때문에, 임의의 값들을 넣어 보았습니다.

노가다의 흔적...

 

이중 for문 시간 측정

 

이중 for문 코드

0.12258195877075195 만큼 걸린다고 측정되네요.

 

for문 안에 고차함수 시간 측정

for문 안에 고차함수를 입력한 코드가 가장 시간이 많이 걸리네요.

1.394997000694275 만큼의 시간이 걸리고, 고차함수에서 210,500 times가 측정이 됩니다.

 

추가로... 시간 초과를 해결했던 코드

    func solution(_ N:Int, _ stages:[Int]) -> [Int] {
        var stageCount = stages.count
        var countArray = Array(repeating: 0, count: N+2)
        var dic = [Int:Double]()

        // 1부터 N까지의 값 count
        for i in stages {
            countArray[i] += 1
        }

        for stage in 1...N {
            let count = countArray[stage]
            if countArray[stage] == 0 {
                dic[stage] = 0.0
            } else {
                dic[stage] = (Double(count)/Double(stageCount))
                stageCount -= count
            }
        }

        var resultArray = [Int]()

        resultArray = dic.sorted {
            if $0.1 == $1.1 {
                return $0.0 < $1.0
            }
            return $0.1 > $1.1
        }
        .map{$0.0}

        return resultArray
    }

시간 초과를 해결하고 정답이었던 코드입니다.

다시 잘 생각해 보니 굳이 이중 for문을 사용하지 않아도 풀 수 있다는 것을 깨달았습니다.

 

0.09998297691345215 만큼 걸린다고 측정되네요.
셋 중 가장 빠른 코드입니다.

 

---

알고리즘을 풀다 보면 항상 이중 for문이 가장 느릴 것이라고 생각하였는데, 막상 시간을 측정해 보니 for문 안에 있는 고차함수가 더 느리다는 것을 알게 되었습니다. (고차함수 좋아하는데!!)

 

고차함수는 코드를 간결하게 작성할 수 있는 장점이 있지만, 시간 복잡도를 계산해야 하는 점, 과도한 고차함수는 코드의 가독성을 해칠 수 있는 점을 유의하면서 사용해야 할 것 같습니다. :)