덧칠하기

최소 페인트칠 횟수 구하기

오늘 배운 것
오늘은 페인트가 벗겨진 벽의 특정 구역에 페인트칠을 최소한의 횟수로 덧칠하는 문제를 풀었다. 벽을 1미터 단위로 나누고, 정해진 구역을 롤러로 페인트칠해야 하는 상황에서 롤러의 길이를 고려하여 최소한의 페인트칠 횟수를 구하는 방법을 학습했다.

문제 접근 방식

롤러 범위 이해: 롤러는 m미터의 길이를 한 번에 칠할 수 있다. 따라서 section 배열에 주어진 페인트칠이 필요한 구역을 순회하면서, 롤러 범위를 넘어서는 위치에서만 새로운 페인트칠을 시작해야 한다.

현재 롤러의 범위 끝 위치 설정: 페인트칠을 할 때마다 롤러가 덮는 범위의 끝 위치를 갱신하고, 다음 구역이 이 범위를 벗어날 때만 추가로 페인트칠을 시작한다.

최소 횟수 카운트: 구역을 순회하면서 현재 롤러의 범위를 넘는 구역이 나타날 때마다 페인트칠 횟수를 증가시키고, 새로운 롤러의 끝 위치를 업데이트한다.

코드 설명

import Foundation

func solution(_ n: Int, _ m: Int, _ section: [Int]) -> Int {
    var count = 0  // 최소 페인트칠 횟수
    var current = 0  // 현재 롤러로 칠할 수 있는 범위의 끝 위치
    
    for s in section {
        // 현재 구역이 롤러 범위를 벗어난 경우, 새로운 페인트칠 시작
        if s > current {
            count += 1  // 페인트칠 횟수 증가
            current = s + m - 1  // 새로운 롤러 범위 끝 위치 설정
        }
    }
    
    return count
}

변수 초기화
count: 페인트칠을 한 횟수를 저장한다.
current: 현재 페인트칠로 커버할 수 있는 범위의 끝 위치를 나타낸다.

구역 순회 및 페인트칠 결정
section 배열을 순회하며 각 구역 s를 확인한다.
s가 current를 넘는 위치에 있으면, 새로운 페인트칠이 필요하므로 count를 증가시키고, 새로운 롤러의 끝 위치 current를 s + m - 1로 설정한다. 이 과정을 통해 최소한의 페인트칠로 모든 필요한 구역을 덮는다.

결과 반환
모든 구역을 순회한 후 최종적으로 필요한 최소 페인트칠 횟수 count를 반환한다.

입출력 예시

예제 1: n = 8, m = 4, section = [2, 3, 6]
구역 3부터 롤러로 덮으면, 2, 3, 4, 5를 칠할 수 있으며, 다음으로 구역 6부터 새로운 롤러를 시작해야 한다.
결과: 2
예제 2: n = 5, m = 4, section = [1, 3]
롤러를 구역 1부터 시작하여, 1, 2, 3, 4를 한 번에 칠할 수 있다.
결과: 1
예제 3: n = 4, m = 1, section = [1, 2, 3, 4]
롤러가 1미터이므로 각 구역을 한 번씩 칠해야 한다.
결과: 4

느낀 점

롤러 범위 관리의 중요성: 롤러가 덮는 범위를 관리하면서 특정 구역에서만 새로운 페인트칠을 시작하는 로직을 설계하는 것이 중요했다. 현재 범위를 추적하고 필요한 구역에서만 페인트칠을 하는 것이 효율적인 풀이의 핵심이었다.
반복문을 통한 최소 조건 처리: section 배열을 순회하며 현재 범위를 체크하는 방법이 간결하고 효율적이어서, 이와 같은 조건이 있는 문제에서 유용한 접근 방식임을 배웠다.
롤러 범위 조건 설정: current를 업데이트하여 페인트칠 범위를 관리하는 과정에서 초기 위치와 롤러 범위를 벗어나는 구역을 정확히 처리하는 조건을 설정하는 데 주의가 필요했다. 특히, s + m - 1로 끝 위치를 정확하게 계산해주어야 중복 칠하지 않도록 할 수 있었다.

이번 문제를 통해 구역의 특정 범위를 관리하고 반복문을 통한 조건 처리를 활용해 효율적으로 문제를 해결하는 방법을 배웠다. 특히, 조건에 맞춰 필요한 시점에서만 새로운 작업을 시작하여 최소화를 추구하는 문제에 대한 접근법을 익힐 수 있었다. 앞으로도 범위 관리가 필요한 문제에서 유용하게 적용할 수 있을 것 같다.