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

사진을 클릭하면 해당 문제로 이동

💡풀이

import java.util.Arrays;
import java.util.stream.IntStream;

class Solution {
    public int solution(int n, int m, int[] section) {
        boolean[] painted = new boolean[n + 1];

        Arrays.fill(painted, true); // n을 1로 채운 배열로 만든다
        for (int s : section) { // section 위치는 0으로 바꾼다
            painted[s] = false;
        }

        int count = 0;

        // section으로 분기한다
        for (int i = 0; i < section.length; i++) {
            if (painted[section[i]]) continue; // 이미 칠해져있다면 넘어간다

            int start, end;
            if (section[i] + m > painted.length) { // 만약 구역 + m 이 범위를 초과한다면
                if (i + 1 < section.length) continue; // 다음 section이 있다면 넘어가고
                start = section[i] - m + 1;
                end = section[i]; // 끝에서 부터 역순으로 칠함
            } else {
                start = section[i];
                end = section[i] + m - 1;
            }
            IntStream.rangeClosed(start, end).forEach(e -> painted[e] = true);
            count++;
        }

        return count;
    }
}

💡풀이 2

- 그리디

class Solution {
    public int solution(int n, int m, int[] section) {
        int roller = section[0];
        int cnt = 1;
        for(int i = 1; i < section.length; i++) {
            if(roller + m - 1 < section[i]) {
                cnt++;
                roller = section[i];
            }
        }
        return cnt;
    }
}

---

GitHub - okjunghyeon/Programmers_CodingTest: 프로그래머스 관련 코딩테스트 문제를 풀이한 저장소입니다.