[프로그래머스] (Swift) kakao - 실패율 (2019 KAKAO BLIND RECRUITMENT)

🟠 문제링크

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

프로그래머스

 

🟠 시간초과 코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Programmers/kakao_%EC%8B%A4%ED%8C%A8%EC%9C%A8/filter%EC%82%AC%EC%9A%A9_%EC%8B%9C%EA%B0%84%EC%B4%88%EA%B3%BC.swift

GitHub - deslog/Algorithm

간단하게, 배열에서 수를 세어서 나눠주는 문제이다. stage별로 failure를 구하는 문제라서, 배열을 두개 만들어서 구하려고 했지만, 메모리+효율성을 위해 딕셔너리를 사용했다. 어차피 key/value 별로 정렬해주면 되니까!

그리고 해당 stage를 달성한사람, 달성했지만 못해결한사람을 세어주기위해 filter+count를 이용해서 세어주었다. 하지만 test case 5, 9, 22번에서 시간초과가 발생했다 ㅠㅠ 

import Foundation

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

    for i in 1..<N+1 {
        let failNum = stages.filter({ $0 == i }).count
        let clearNum = stages.filter({ $0 >= i }).count
        failure[i] = Double(failNum) / Double(clearNum)
    }
    let sortArr = failure.sorted(by: <).sorted(by: { $0.1 > $1.1 })
    let result = sortArr.map{ $0.key }
    
    return result
}

 

인터넷을 찾아보니, 테스트케이스가 추가되면서 5, 9, 22 번에서 시간초과가 뜨는 사람들이 많았다. 문제는, filter 고차함수가 for 문 안에 들어가면 시간복잡도가 너무 커지기 때문에, filter를 빼고 count해보라는 조언이 있었다.

 

🟠 정답 코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Programmers/kakao_%EC%8B%A4%ED%8C%A8%EC%9C%A8/main.swift

GitHub - deslog/Algorithm

그래서 위 코드와 같은 방식으로, filter를 사용하지 않고 배열을 사용해서 count 해주었다. index번호를 그대로 stage 번호로 가져가고, 등장하면 index에 맞춰서 +1 씩 해주면서 count 해주었다. 이런 방식으로 문제를 푸니, 통과였다!

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    var failure = [Int: Double]()
    var total = Double(stages.count) // 8.0
    var countArr = Array(repeating: 0, count: N+2) // [0, 0, 0, 0, 0, 0]

    for num in stages {
        countArr[num] += 1 // [0, 1, 3, 2, 1, 0, 1]
    }

    for i in 1..<N+1 {
        if countArr[i] == 0 {
            failure[i] = 0.0
        } else {
            total = total - Double(countArr[i])
            failure[i] = Double(countArr[i]) / total
        }
    }
    let sortArr = failure.sorted(by: <).sorted(by: { $0.1 > $1.1 })
    let result = sortArr.map{ $0.key }

    return result
}

 

애초에 각 스테이지 별로 개수를 세어주고 난뒤 for문을 돌려주면, 선형적인 시간복잡도로 해결이 가능하지만, for문안에 filter를 넣게 되면, O(n^2) 까지 시간복잡도가 커지기 때문에, 특정 케이스가 큰 것들은 통과하지 못했던 것이다.

 

---

🟠 고찰

애플 아카데미에서 좋은 기회로 애플 관계자분께 질문할 수 있는 기회가 있었고, 이때 알고리즘 관련 질문한 적이 있었다. '고차함수'에 대한 대화를 진행했었고, 알고리즘을 풀 때 왜 고차함수를 쓰면 효율성이 떨어지고, 시간초과가 자주나는지에 대해서 여쭤보았다.

그 분께서는 절대 swift에서 효율성이 떨어지게 고차함수를 만들어놓지 않았다며, 내가 짠 알고리즘에 문제가 있는 경우라고 하셨다. 인터넷을 찾아보니 map, filter, reduce 각 고차함수는 O(n)의 시간복잡도를 갖고있다. 별로 그닥 큰 건 아닌거같지만, 이게 for 문 안에 들어있으면, 시간복잡도가 기하급수적으로 늘어나기때문에 방금과 같은, 시간효율성이 떨어지는 문제를 겪었던 것이다. 

아하! 그래서 알고리즘 문제를 풀 때는 대부분 고차함수를 쓰지말라는거구나!! 왜냐면 대부분 for 문을 사용하니까..! 나도 앞으로는 단독으로 사용할때 외에는 고차함수를 사용하는 것을 조심해야겠따!