문제링크

문제 이해

[ 입력형태 / 조건 ]

n
벽을 1미터 길이의 구역 n개 | 8 | 1 ≤ m ≤ n ≤ 100,000

m
벽에 페인트를 칠하는 롤러의 길이는 m미터 | 4 | 1 ≤ m ≤ n ≤ 100,000

section
다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 | [2, 3, 6] | 1 ≤ section의 길이 ≤ n, 1 ≤ section의 원소 ≤ n, section의 원소는 페인트를 다시 칠해야 하는 구역의 번호, 같은 원소가 두 번 이상 나타나지 않음, 원소는 오름차순으로 정렬

[ 문제 ]

롤러로 페인트칠해야 하는 최소 횟수를 return

[ 풀이 ]

n을 전체 순회하면서 section에 속한 값과 일치하면 ans를 증가

---

코드

> [성공] 1차 시도 : 구현

• 생각한 풀이 그대로 구현

class Solution {
    public int solution(int N, int M, int[] section) {
        int ans = 0, secLen = section.length, i=0;
        for(int n=1; n<=N; n++){
            if(i<secLen){
                if(n == section[i]){
                    ans++;
                    n+=M-1;
                    while(i<secLen && section[i] <= n){
                        i++;
                    }
                }
            }else
                break;
        }
        return ans;
    }
}

> [성공] 2차 시도 : 구현

• n을 전체 순회하는 것보다 section 순회하는 것이 시간을 줄일 수 있을 것이라 생각

class Solution {
    public int solution(int n, int m, int[] section) {
        int ans = 0, max = 0;
        for (int sec : section) {
            if (max <= sec) {
                max = sec + m;
                ans++;
            }
        }
        return ans;
    }
}

Tip : 전체를 순회하지 않고 일부만 순회해도 전체를 순회한 효율을 낼 수 있는 문제들도 있다.