[programmers] 덧칠하기 - Java

덧칠하기

문제 설명

• 롤러가 벽에서 벗어나면 안 됩니다.

• 구역의 일부분만 포함되도록 칠하면 안 됩니다.

제한사항

• 1 ≤ m ≤ n ≤ 100,000

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

입출력 예

입출력 예 설명

• 예제 1번은 2, 3, 6번 영역에 페인트를 다시 칠해야 합니다. 롤러의 길이가 4미터이므로 한 번의 페인트칠에 연속된 4개의 구역을 칠할 수 있습니다. 처음에 3, 4, 5, 6번 영역에 페인트칠을 하면 칠해야 할 곳으로 2번 구역만 남고 1, 2, 3, 4번 구역에 페인트칠을 하면 2번 만에 다시 칠해야 할 곳에 모두 페인트칠을 할 수 있습니다.



2번보다 적은 횟수로 2, 3, 6번 영역에 페인트를 덧칠하는 방법은 없습니다. 따라서 최소 횟수인 2를 return 합니다.

• 예제 2번은 1, 3번 영역에 페인트를 다시 칠해야 합니다. 롤러의 길이가 4미터이므로 한 번의 페인트칠에 연속된 4개의 구역을 칠할 수 있고 1, 2, 3, 4번 영역에 페인트칠을 하면 한 번에 1, 3번 영역을 모두 칠할 수 있습니다.



따라서 최소 횟수인 1을 return 합니다.

• 예제 3번은 모든 구역에 페인트칠을 해야 합니다. 롤러의 길이가 1미터이므로 한 번에 한 구역밖에 칠할 수 없습니다. 구역이 4개이므로 각 구역을 한 번씩만 칠하는 4번이 최소 횟수가 됩니다.



따라서 4를 return 합니다.

solution.java

import java.util.*;

class Solution {
    public int solution(int n, int m, int[] section) {
        int start = section[0];
        int end = section[0] + (m-1);
        int ans = 1;
            
        for(int i : section){
            if(i>=start && i<=end)
                continue;
            else{
                start = i;
                end = i + (m-1);
                ans++;
            }
            
        }
        return ans;
    }
}

핵심 키워드

1. start 변수를 첫 번째 섹션의 시작 인덱스로 초기화하고, end 변수를 첫 번째 섹션의 끝 인덱스로 초기화한다.

2. 배열을 반복하면서 각 원소를 확인한다.

3. 현재 원소가 현재 섹션에 속하는지 확인한다. 속한다면 건너뛰고 다음 원소를 확인한다.

4. 현재 원소가 현재 섹션에 속하지 않는다면, 새로운 섹션을 시작하게 되므로 start를 현재 원소의 인덱스로, end를 start에서 m-1을 더한 값으로 갱신하고, ans를 1 증가시킨다.

결론!