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

📖 문제 설명

어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.

넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.

벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.

• 롤러가 벽에서 벗어나면 안 됩니다.
• 구역의 일부분만 포함되도록 칠하면 안 됩니다.

즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.

한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.

정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.

---

🚫 제한 사항

•  1 ≤ m ≤ n ≤ 100,000
• 1 ≤ section의 길이 ≤ n
  
  • 1 ≤ section의 원소 ≤ n
  • section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
  • section에서 같은 원소가 두 번 이상 나타나지 않습니다.
  • section의 원소는 오름차순으로 정렬되어 있습니다.

---

💾 입출력 예시

 

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

---

⌨️ 나의 풀이 (코드)

 

문제 풀이에 앞서 의사 코드를 작성해 생각을 정리했다.

 

1. section을 통해 페인트칠을 할 구역을 특정 (section의 원소는 오름차순으로 정리되어 있음) 
2. section 첫 번째 요소에서 시작 => 롤러 m의 길이만큼 전진 (전진 중 다른 요소가 있다면 삭제)
3. 구획 도달이 안된다면 새로운 출발점을 특정, 반복 (반복마다 반환할 count값 + 1)

 

이후 의사코드를 기반으로 코드를 작성했다.

 

매개변수 section의 배열값을 고려해 최초의 요소로부터 "롤러의 길이만큼 전진, 확인, 반복"하는 부분을 어떻게 구현하는지가 관건이었다. 해당 로직을 구현하기 위해 매개변수를 오염시키지 않고요소가 발견될 때마다 해당 요소부터 배열에서 삭제시키는 .shift() 메서드와 순회 횟수를 제한하는 for문을 활용했다.

 

function solution(n, m, section) {
  let count = 0;
  const target = [...section];
  while (target.length > 0) {
    count++;
    for (let i = 0; i < m; i++) {
      if (section.includes(section[0] + i)) {
        target.shift();
      }
    }
  }

  return count;
}

 

위의 코드는 실패했다.

 

찬찬히 코드를 살펴보니 비교에 활용중인 target 배열의 요소를 삭제시키기 때문에 section[0]번쨰 요소는 변하지 않아 테스트가 실패하고 있었다. 여기에 더해 이럴 경우 section 배열은 .shift() 메서드를 활용해 요소를 삭제시키지 않아 런타임이 오래 걸리는 단점도 발견됐다.

 

function solution(n, m, section) {
  let count = 0;
  const target = [...section];
  while (target.length > 0) {
    let temp = target[0];
    count++;
    for (let i = 0; i < m; i++) {
      if (target.includes(temp + i)) {
        target.shift();
      }
    }
  }

  return count;
}

 

이에 따라 순회하는 배열의 첫 번째 요소가 삭제되어도 문제가 없도록 temp라는 임시 변수를 선언 및 할당 후 temp 변수의 생명주기만큼 순회할 수 있도록 for문을 활용해 로직을 재구성했다. 위의 코드를 통해 순회하는 배열의 길이를 점차 줄여나가 테스트의 시간도 단축해 코드의 효율성을 높일 수 있었다.

 

테스트 시간이 60% 정도 단축되었다

 

---

📝 Note

 

다른 사람의 풀이에서 ES6 문법을 활용해 보다 모던한 코드를 보았다.

 

function solution(n, m, sections) {
    var answer = 0;
    var painted = 0;
    for(var section of sections) {
        if(painted < section) {
            answer++;
            painted = section+m-1;
        }
    }
    return answer;
}

 

for of 반복문을 통해 매개변수 sections를 순회하고, 이 과정에서 painted 변수를 통해 sections 배열 안의 요소 값만큼 "전진"했다. 

 

예를 들어, n = 5, m = 4, sections = [1, 2, 3, 5]라는 예시가 주어졌다면...

 

1) 첫 번째 요소 1 에서 시작, painted = 1 + m (4) - 1 = 4 가 된다. (answer = 1)
2) 두 번째 요소 2 는 painted (4)보다 작으므로 if문 생략, 같은 방식으로 3도 생략 (answer = 1)
3) 네 번째 요소 5 는 painted (4)보다 크므로 다시 한 번 if문 내 코드 실행 (answer = 2, painted = 8)
4) for of 순회 종료, answer 반환

 

 

이 경우 매개변수 sections의 배열만을 순회하면 되므로 코드 효율을 획기적으로 높일 수 있다.