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

 

 

📑 1. 문제설명

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

1. 문제 요약

• 벽 길이 = n (1m 단위 구역으로 나눔, 번호 1~n)
• 롤러 길이 = m (한 번 칠하면 연속 m칸이 칠해짐)
• 반드시 다시 칠해야 하는 구역 = section 배열

조건

1. 롤러는 벽 밖으로 나가면 안 됨
2. 구역은 부분만 칠할 수 없음. (롤러 시작 위치는 항상 구역 경계에 맞춰야 함)
3. 이미 칠한 구역은 다시 칠해도 됨
4. section에 포함된 구역은 최소 한 번은 칠해야 함
5. 최소 롤러 사용횟수 리턴

---

💡 2. 풀이과정

풀이 1

n크기 만큼 boolean[] 배열을 선언해서 section 배열에 담긴 숫자 - 1에 해당하는 인덱스만 true로 바꾸었다.

그리고 section을 순회하면서 boolean[]에서 i번째부터 m칸 칠한 부분을 false로 바꾸기

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        // boolean 배열 선언하고 section에 든 인덱스만 true로 바꾸기 
        boolean[] painted = new boolean[n];
        for (int i = 0 ; i < section.length; i++) {
            painted[section[i] - 1] = true;
        }
        
        for (int i = 0; i < n; i++) {
            if (painted[i]) {
                // i부터 m칸을 칠했다고 가정 → false로 갱신
                for (int j = i; j < i + m && j < n; j++) {
                    painted[j] = false;
                }
                answer++;
            }
        }
        
        return answer;
    }
}

 

하지만 내가 푼 것처럼 굳이 모든 칸을 관리할 필요가 없고, 어디까지 칠했는지 위치만 paintedEnd라는 인덱스로 알면 된다.

---

👨‍💻 3. 정답코드

import java.util.*;

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int paintedEnd = 0; // 마지막으로 칠해진 구간의 끝 위치

        for (int s : section) {
            // 아직 안 칠해졌다면
            if (s > paintedEnd) {
                answer++;
                paintedEnd = s + m - 1; // 이번에 칠할 수 있는 끝 위치
            }
        }

        return answer;
    }
}

1. 처음에는 마지막으로 칠해진 구간 끝 위치를 0으로 잡기
2. section을 순회하면서 s > paintedEnd라면 answer++
3. paintedEnd = s + m -1 로 이번에 칠할 수 있는 끝 위치 업데이트
   • 여기서 s + m이 아니라 s + m - 1인 이유는 첫시작점 포함이기 때문

예를 들면,

n = 8, m = 4
section = [2, 3, 6]

• s = 2 → paintedEnd = 0 → 2 > 0 이므로 칠함 → answer=1, paintedEnd=5
• s = 3 → 3 <= 5 이므로 이미 칠해짐 → 패스
• s = 6 → 6 > 5 이므로 칠함 → answer=2, paintedEnd=9
• 최종 answer = 2