프로그래머스 - 제일 작은 수 제거하기, 시간초과 해결

좋은 코드를 만들기 위해 메서드의 시간복잡도를 이해하는 것은 중요합니다

 

다음과 같은 코드는 시간 초과가 발생하는 코드입니다.

당연한거지만 실수할 수 있으므로 하나하나 뜯어보는 습관이 중요합니다.

 

filter 클로저 내부에 min 을 사용해버리면 filter 의 시간복잡도는 O(n) 이고 min 또한 O(n) 이므로 O(n^2)이 되어 버립니다.

func solution(_ arr:[Int]) -> [Int] {
    let result = arr.filter { $0 != arr.min()! }
    return (result.isEmpty || result.count == 1) ? [-1] : result
}

 

이를 해결하기 위해서는 min 을 한번만 사용할 수 있도록 다음과 같이 구현합니다.

func solution(_ arr:[Int]) -> [Int] {
    let m = arr.min()!
    let result = arr.filter { $0 != m }
    return (result.isEmpty || result.count == 1) ? [-1] : result
}