프로그래머스 코딩테스트 연습 - 덧칠하기 JavaScript

붓을 이용하여 덧칠을 하는데, 최소한의 붓질만으로 덧칠을 하는 컨셉의 문제이다.

function solution(n, m, section) {
    const check = (arr) => {
        let response = 0;
        while(arr.length > 0) {
            let start = arr.shift();
            response++;
            while(arr[0] < start + m) {
                arr.shift();
            }
        }
        return response;
    }
    return check(section);
}

문제를 해결하기 위해서 생각해낸 컨셉은 앞의 덧칠이 필요한 부분을 시작으로 붓의 길이만큼을 고려하여, 덧칠을 한 뒤 다음 덧칠이 필요한 부분을 찾아 같은 로직을 반복하는 것 이었다.

사실, 이 로직만으로는 문제가 해결이 되지 않을 것으로 생각했으나 생각보다 손쉽게 해결이 되어버렸다.

내 생각엔 그때그때 최적의 결과를 생각해내는 그리디 방식이 이 문제에 적용되지 않았나 싶다.