[프로그래머스] 덧칠하기 (JS)

 

문제 링크

프로그래머스

 

문제 해석

문제는 벽에 페인트를 다시 칠해야 하는 구역들이 주어졌을 때, 최소한의 횟수로 페인트칠을 하는 방법을 찾는 것이다.

벽의 길이는 `n` 미터이며, 각 구역은 1미터씩 나누어져 있고, 롤러의 길이는 `m` 미터이다.

페인트칠을 할 수 있는 최소 횟수를 구해야 한다.

 

접근 방법

1. 페인트칠이 필요한 구역 파악하기:
주어진 `section` 배열은 페인트칠이 필요한 구역의 번호를 담고 있다. 이 배열의 각 요소는 구역 번호를 나타낸다.
  
2. 롤러의 범위 확인:

롤러는 한 번에 연속된 `m`미터를 칠할 수 있으므로, 한 번의 칠로 여러 구역을 덮을 수 있다. 목표는 최소한의 칠로 `section` 배열의 모든 구역을 덮는 것이다.
  
3. 탐색 및 칠하기:

벽의 1번 구역부터 시작해 페인트칠이 필요한 구역을 발견하면, 롤러를 이용해 해당 구역부터 `m`미터 범위를 칠한다. 그 후, `section` 배열에서 칠해진 구역들을 제거한다.

4. 페인트칠 횟수 증가:

새로운 칠이 시작될 때마다 페인트칠 횟수를 증가시키고, 모든 필요한 구역이 칠해질 때까지 이를 반복한다.

 

 

코드 설명

function solution(n, m, section) {    
    let paint = 0; 
    
    for (let i=1; i<=n; i++) {
        if (section[0] === i) {
            paint++; 
            section.splice(0,1); 
            for (let j=i+1; j<i+m; j++) {
                if (section[0] === j) section.splice(0,1);
            }
        }
    }
    
    return paint; 
}

 

결론

이 문제는 효율적으로 구역을 덮는 방법을 찾는 탐욕 알고리즘의 한 예로 볼 수 있다.

나는 페인트칠 횟수를 최소화하기 위해 롤러의 길이를 고려해 페인트칠을 할 수 있는 최대 범위를 탐색하며 문제를 해결하였다.