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

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

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

입력
n : 벽의 길이
m : 롤러의 길이
section : 최소한 한 번이라도 덧칠해야 하는 벽의 배열
 
출력
롤러로 페인트칠 해야 하는 최소 횟수
 
제한사항

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

풀이

이 문제는 section을 한 번 순회하며 롤러로 칠해야 하는 부분이 section의 원소에 포함되어 있지 않는 경우 롤러를 더 칠해야 하는 문제이다. 다시 말해 section의 원소 하나를 정하고 이 원소를 기준으로 그 다음 section 원소가 롤러의 길이 보다 짧다면 넘어가고 그렇지 않다면 롤러를 칠하는 횟수를 증가시키고 다시 section의 원소를 갱신하는 과정을 반복한다.
말이 어렵다. 예시와 그림으로 보자
 

section[0]을 기준으로 둔 뒤에 그 다음 원소인 section[1]과 값을 비교한다. section[0]과 롤러의 길이 m의 차이가 section[1]보다 크거나 같으면 인덱스만 증가하고 그렇지 않으면 롤러를 칠하는 횟수가 증가한다.
이 때 section을 그냥 순회할 수 있는 이유는 section 안의 원소가 오름차순으로 정렬되어 있기 때문이다. 꼭 봐야한다.
 
시간복잡도는 배열을 한 번 순회하는 데 걸리는 시간인 O(n),
공간복잡도는 n, m, section ,인덱스, 횟수, 기준을 저장하니 O(n)이다. (배열의 크기이다.)

코드

function solution(n, m, section) {
    var answer = 1;
    let idx = 0;
    let target = section[idx];
    
    while (idx<section.length) {
        idx++;
        if (section[idx] > target+m-1) {
            answer++;
            target = section[idx];
        }
    }
    return answer;
}

 
다른 사람의 풀이를 보니 굳이 while문을 사용하지 않고 for..of문을 사용해도 더 좋았을 것 같다.