[Programmers] 덧칠하기 - Java

문제

프로그래머스

 

풀이

그리디 유형의 문제이다.

1. 색칠하는 횟수를 최소화하려면, 색칠된 부분을 다시 색칠할 필요가 없다는 것이라고 생각했다. 즉 그냥 skip 해버리면 된다는 생각을 했다.

2. skip을 하려면 어떤 구역에서 m칸 만큼 색칠하고 그 다음 구역 번호(paintPoint)를 알아야할 필요가 있다고 생각했다. (sections[i] + m부터 덧칠해야하는 구역 번호가 있다면 덧칠한다.)

3. paintPoint보다 현재 덧칠해야하는 구역 번호가 더 작으면, 이미 색칠이 된 것이므로, continue를 통해서 계속 i를 증가시킨다.

4. 색칠할때, 색칠 횟수를 기록한다.

 

소스코드

class Solution {
    public int solution(int n, int m, int[] section) {
        //색칠될 수 있는 시작 구역 번호
        int paintPoint = 0;
        int answer = 0;
       
        for (int i = 0; i < section.length; i++) {
            //section[i]가 이전에 덧칠해 있을 경우
            if (paintPoint > section[i]) {
                continue;
            }
            
            //색칠될 수 있는 시작 구역 번호 갱신
            paintPoint = section[i] + m;
            
            //색칠 횟수
            answer += 1;
        }
       
        return answer;
    }
}