덧칠하기

https://school.programmers.co.kr/learn/courses/30/lessons/161989

코드

function solution(n, m, section) {
    let cnt = 0, lastPaint = section[0] - 1;
    
    section.forEach((v)=>{
      if (v > lastPaint) {
          cnt++;
          lastPaint = v + m - 1;
      }
    })
    
    return cnt;
}

풀이

이중 반복문을 사용해도 통과는 되지만, 너무 오래 걸려 올바른 방법이 아니라고 생각했다.

대신, 이미 칠한 영역보다 다음 칠해야 할 영역이 크면 다음 칠해야 할 영역 + m - 1로 lastPaint 값을 재할당했다. 예를 들어, n = 8, m = 4, section = [2, 3, 6]이 주어졌다면, 전체 영역은 다음처럼 나온다.

1	2	3	4	5	6	7	8
O	X	X	O	O	x	O	O

lastPaint 초깃값은 section[0] - 1 = 1이며, 이 다음 영역 2에서 페인트 칠을 시작해야 한다. 페인트 칠이 가능한 영역은 2, 3, 4, 5까지로, 다음 lastPaint는 5가 된다(v + m - 1). 3은 앞서 칠해졌으므로, 6을 판단한다. lastPaint보다 크므로 cnt를 늘린다. lastPaint가 바뀌지만, 반복문이 끝나 cnt를 반환한다.