[Swift][프로그래머스] - 덧칠하기

💻 프로그래머스: 덧칠하기 - 문제 링크

---

첫 코드: 시간초과

import Foundation

func solution(_ n:Int, _ m:Int, _ section:[Int]) -> Int {
    var copyArr: [Int] = section
    var returnCount = 0
    
    while copyArr.count > 0 {
        var minNum = copyArr.min()!
        var newArr = copyArr.filter{$0 < minNum + m }.compactMap{Int($0)}
        copyArr = [Int](Set(copyArr).subtracting(Set(newArr)))
        returnCount += 1
    }
    return returnCount
}

풀이 자체는 맞는 것 같은데 시간초과가 났다

주된 원인

1. min 메서드의 불필요한 사용: 문제에서 section 배열은 오름차순 정렬이 되어있다고 했는데, 쓸데없이 사용. .min() .max() 메서드는 배열 전체를 순회하므로 O(n)의 시간복잡도 가짐
2. filter, compactMap 역시 배열 순회하므로 O(n)의 시간복잡도 가짐
3. Set() 생성 및 집합 처리도 O(n)의 시간복잡도 가짐

이 3개의 원인이 반복문마다 반복되므로, 최악의 경우 O(n^2)의 시간복잡도를 가진다.

해결 방안

: 슬라이딩을 이용하여 배열을 한번만 순회해 O(n)의 시간복잡도로 끝낸다

수정 코드

import Foundation

func solution(_ n:Int, _ m:Int, _ section:[Int]) -> Int {
    let len = section.count
    var current = 0
    var count = 0

    while current < len {
        let curVal = section[current]

        while current < len && section[current] < curVal + m {
            current += 1
        }

        count += 1
    }

    return count
}

current < len 을 검사하는 부분은 사실상 O(1)의 시간복잡도를 가지기 때문에, 이렇게 하면 O(n)의 시간복잡도를 가지게 할 수 있다.