<swift> 코딩테스트 시간 초과

코딩테스트 연습을 하다보면 깔끔한 코드가 최고인것 처럼

고차함수를 남발하게 된다.

그러다가

2019 KAKAO BLIND RECRUITMENT 실패율 문제를 풀다가

시간초과라는 충격적인 결과가 나왔다.

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

    // 실패율 계산 후 저장
    for i in 1...N{
        // 도달한 수
        let a = stages.filter{$0 >= i}.count

        // 클리어한 수
        let b = a - stages.filter{$0 > i}.count

        // 실패율
        let failCount = Double(b) / Double(a)

        fail[i] = failCount
    }

    // 실패율이 높은 순서대로 내림차순 숫자 등록, 실패율이 같으면 오름차순
    let failSorted = fail.sorted(by: <).sorted(by: {$0.value > $1.value})

    return failSorted.map{$0.key}
}

위의 소스처럼 고차함수를 남발한 것인데

(위의 소스처럼 하진 않았지만 좀더 시간이 오래 걸리는 케이스여서 가져온 소스)

​

https://zeddios.tistory.com/648

​

제드님의 블로그에서 나오는 것처럼 swift의 고차함수는 시간을 매우 잡아 먹는 듯하다

​

따라서 sort를 두번 하지 않아도 되도록 dictionary를 이차 배열로 바꾸었고

이 이외에 filter 대신 좀더 긴 소스지만 고차 함수를 쓰지 않는 방향으로 바꾼 소스이다.

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    
    var countArray = Array.init(repeating: 0, count: N) // 각 스테이지 당 같혀 있는 사람들의 수
    var probabilityArray = Array.init(repeating: (Int(0), Double(0.0)), count: N) // 스테이지, 실패율
    var total = stages.count // 각 스테이지를 도전한 사람

    for element in stages {
        guard element != N+1 else { // 모두 통과 했다면 배열에 넣지 않음
            continue
        }
        countArray[element-1] += 1
    }

    for stageNum in 1...N {
        let value = countArray[stageNum-1] // 각 스테이지 클리어하지 못한 사람
        probabilityArray[stageNum-1] =  total == 0 ? (stageNum, 0) : (stageNum, Double(value) / Double(total))
        total -= value

    }
    
    probabilityArray = probabilityArray.sorted(by: { $0.1 == $1.1 ? $1.0 < $1.0 : $0.1 > $1.1 })
    // 실패율이 같다면 스테이지 번호가 작은 순서대로 아니라면 실패율이 큰 순서로 정렬

    return probabilityArray.map{$0.0}
}

테스트 4만 봐도

6800.36ms이 53.45ms​으로 바뀐 것을 볼 수 있다.

어마어마한 차이 ㅋㅋㅋㅋㅋㅋㅋ

​

코딩 테스트를 할 때 간단한 코드라면

고차함수를 쓰는 것도 좋지만

이러한 시간이 오래 걸리는 소스는

깔끔한 소스보다는 시간에 중점을 두어 코딩해보면 좋을 것 같다.

 

더 많은 코딩테스트 예제 정보를 얻고 싶다면

blog.naver.com/p41155a/222035899407