문제 풀이 아이디어

문제의 길이와 복잡한 예시에 약간 쫄을(?) 수도 있으나 풀어보면 평범한 그리디 문제입니다. 애초에 n이 최대 0,000이므로 O(n) 이하의 시간 복잡도를 가진 알고리즘으로 풀어줘야 합니다. 1번 구역부터 순회하면서 덧칠이 필요한 구역을 만나면 색칠을 해줍니다. 색칠을 할 때마다 색칠한 횟수를 세어주면 됩니다.

코드

배열을 사용한 풀이

벽은 일종의 수직선이므로 배열을 사용하면 직관적으로 풀 수 있습니다. 다만 실행시간이 일반적인 풀이 보다 더 소요됩니다.

func solution(_ n:Int, _ m:Int, _ section:[Int]) -> Int {

    // 벽 구현
    var walls = Array(repeating: false, count: n + 1)
    var ans = 0

    // 덧칠이 필요한 부분을 true로 표시
    for s in section {
        walls[s] = true
    }

    // 벽을 순회하면서
    for i in 1...n {
        // 칠해야 하는 곳을 만나면
        if walls[i] {
            // m 크기 만큼 색칠한다.
            for j in i..<(i + m) {
                guard j <= n else { break }
                walls[j] = false
            }
            ans += 1
        }
    }

    return ans
}

더 빠른 풀이

덜 직관적이지만 실행속도는 더 빠릅니다.

func solution(_ n:Int, _ m:Int, _ section:[Int]) -> Int {

    // 1 ~ painted = 이미 칠해진 영역
    var painted = 0
    var ans = 0

    // 칠해야 하는 구역을 순회하면서
    for s in section {
        // 아직 해당 구역이 칠해지지 않았다면
        if painted < s {
            // 해당 구역을 시작점으로 m 크기만큼 색칠
            painted = s + m - 1
            ans += 1
        }
    }

    return ans
}