프로그래머스: 덧칠하기

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

프로그래머스

설명

나의 풀이 방법

다시 칠하기로 정한 section 배열의 값을 돌면서 이동한다.

시작점은 section의 0번째 index부터 시작해서 롤러의 길이만큼 이동하면서 방문 표시한다.

사이클을 한번 돌면 answer를 1증가한다.

 

이 다음 사이클에서는 

section의 1번째 index가 시작점이 된다. 만약 방문했다면 넘어간다.

=> 즉, section 배열에 있는 값을 확인하기 위해 visited 배열을 만들어서 관리했다.

 

class Solution {
    // n: 벽의 번호, m: 롤러의 길이, section: 다시 칠해야하는 곳
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        boolean[] visited = new boolean[n+1];
        
        int start = 0;
        
        for(int i = 0; i < section.length; i++) {
            int s = section[i];
            if(visited[s]) {
                continue;
            }
            answer++;
            for(int now = s; now < s+m; now++) {
                if(now > n) {
                    break;
                }
                visited[now] = true;
            }
        }
            
        return answer;
    }
}

 

다른 풀이 방법(visited 배열 사용 X)

다른 방법은 한번 롤러로 벽을 칠했을 때, 끝점을 maxPainted 변수라고 표시하고 

section 배열에 있는 값들이 maxPainted보다 작을 때, maxPainted 값을 m만큼 업데이트하는 방식이다.

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