[프로그래머스] 덧칠하기 - 자바스크립트

 

문제

프로그래머스

 

---

코드

function solution(n, m, section) {
   var answer = 0;
   const rollerLen = m - 1;
   let base = section[section.length - 1];
   let cur;

   answer += 1;

   while (section.length) {
     cur = section.pop();

     if (base - cur <= rollerLen) continue;
     base = cur;
     answer += 1;
   }

   return answer;
 }

 

---

풀이

문제조건

페인트가 칠해진 길이 n미터 벽이 있다.
벽 전체에 페인트칠하는 것 대신, 일부만 칠하기로 한다.
벽을 1미터로 n개 구간으로 나누고, 칠해야 할 구역을 정해보자.

 

페인트 칠하는 롤러는 m미터이고,
 - 롤러가 벽에서 벗어나면 안된다.
 - 구역 일부분만 포함되도록 칠하면 안된다.

 

동일한 구역에 페인트를 여러번 칠해도 되지만, 페인트칠 횟수를 최소화하자.

 

제한사항

 1<=m <= n <= 100,000
 1<= section(페인트 칠해야 할 구역의 번호가 담긴 정수배열) <= n
 1<= section 원소 <= n
section의 원소는 중복 x, 오름차순 정렬이 되어 있다.

 

풀이방향

어떻게 칠하는게 효과적일까?

 

우선 머리를 굴려본다.

현재 롤러 m크기를 기준으로,,

section을 제일 왼쪽위치 혹은 오른쪽 위치에서 반대방향으로 이동하면서
현재 위치부터 롤러m 크기에 있는 모든 가능한 구역을 칠해준다.

- 롤러크기가 1이면, 현재위치만 칠할 수 있다.
- 롤러크기가 3이면, 현재위치 + 최대 2거리만큼 칠해줄 수 있다.

 

그럼 고민할 게 없다. 그리디 문제다.

제일 왼쪽/오른쪽에서 시작해서 더이상 칠할 section이 없으면 최소로 칠한 것이다.

 

while문을 통해 section에 원소가 없어질 때 까지 순회한다.

탐색의 첫 시작이 왼쪽인지 오른쪽인지는 중요하지 않다.

while을 활용하기로 했으니, Array.prototype.pop 메서드로 오른쪽을 칠하는 기준으로 삼아보자.

- for문을 활용했다면, 왼쪽으로 기준을 삼아도 되고, 오른쪽을 삼아도 된다.

- 사실 while문을 활용해도, 내림차순 sort하고 pop을 하여 왼쪽을 기준삼아도 된다.

- 그러나 while문을 활용하면서, 오름차순 sort 상태에서 shift 메서드로 할 생각은 접어두길 바란다.

    (왜인지 잘 모르겠다면 shift 메서드의 시간복잡도를 생각해보길 바란다.)

 

---

주석 포함 코드

// while문을 활용할거라 변수 n은 쓸데가 없다.

function solution(n, m, section) {
   var answer = 0;
   // 거리(m)과 while문 내의 부등호는 연관이 깊다.
   // 나는 m=1일 때 기준 값만 칠해지므로 1을 빼준 값을 rollerLen으로 정했다.
   const rollerLen = m - 1;
   let base = section[section.length - 1];
   let cur;

   answer += 1;

   while (section.length) {
     cur = section.pop();
     
	 // base-cur <= rollerLen이면 아직 더 칠할 수 있다.
     // 만약 여기서 continue에 부합되지 않았다면, 현재 cur부터 base를 잡아 칠해야하므로
     // base를 cur로 바꿔주고 answer를 증가시켜준다.
     // 이런 문제들은, 항상 진입점과 탈출점(section 원소가 1개 남았을 때)에서
     // answer를 1 증가시키거나 증가시키지 않는 경우들을 잘 생각해서 코드를 짜야한다.
     if (base - cur <= rollerLen) continue;
     base = cur;
     answer += 1;
   }

   return answer;
 }