[프로그래머스] Lv2. 덧칠하기 - Javascript

# 문제

• 길이가 n인 벽에 페인트를 덧칠하려고 한다
• 페인트 칠하는 롤러의 길이는 m 미터
• 롤러로 페인트칠 하는 최소 횟수 반환

# 정의

• 롤러가 벽에서 벗어나면 안됨
• 구역의 일부분만 포함되도록 칠하면 안됨
• 한 구역을 여러 번 칠할 수 있음

# 제한사항

• 1 <= m <= n <= 100,000
• 1 <= section의 길이 <= n
  • 원소는 페인트를 다시 칠해야하는 구역의 번호이며, 중복 없이 오름차순으로 정렬되어 있음

# 입출력 예

• n: 8
  m: 4
  section: [2, 3, 6]
  result: 2
• n: 5
  m: 4
  section: [1, 3]
  result: 1
• n: 4
  m: 1
  section: [1, 2, 3, 4]
  result: 4

# 풀이

벽의 길이 n이 최대 10만이기 때문에 O(N) 혹은 O(NlogN) 으로 풀어야 하는 문제이다.
처음에는 DP로 접근하려다가, 생각해보니 그리디 방식으로 풀어도 되겠다는 각이 나왔다.
칠해야 하는 구역은 어찌됐든 반드시 칠해져야하기에 section을 처음부터 탐색하면서 section에 해당하는 부분을 만나면 count를 증가시키고 탐색하고자 하는 곳을 m 만큼 점프시키는 방식으로 해결했다.

function solution(n, m, section) {
    // section을 탐색하되 count와 target 변수를 다루고 싶어서 reduce를 사용했다.
    // 탐색하는 과정에서만 필요한데 굳이 solution 함수 내에 변수를 선언할 필요가 없다는 것도 이유
    const { count } = section.reduce((acc, value) => {
        // section의 첫 번째 값으로 target으로 초기화시킨 뒤
        // target의 위치가 탐색값 이하라면 현재 section값 + 롤러 길이로 target을 갱신시켜준다.
        // 그러면 롤러 크기 안에 들어오는 section에 대해서는 바라보지 않고 스킵하게 된다.
        if(acc.target <= value) {
            return { count: acc.count + 1, target: value + m };
        }
        return acc;
    }, { count: 0, target: section[0] });
    return count;
}