[프로그래머스/JAVA] 덧칠하기

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도
• 👩🏻‍💻 다른 풀이 (커서를 두는 그리디 풀이)

 

 

 

🔗 문제 바로가기

 

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

프로그래머스

 

---

📌 문제 요약

 

 

 

🎨 롤러로 벽 칠하기

🖌️ 페인트칠 규칙

• 롤러의 길이는 m 미터이다. (즉, 한 번 칠할 때 m 개의 연속된 구역을 한 번에 칠할 수 있다.)
• 롤러의 양 끝은 구역 경계나 벽의 끝에 맞춰야 한다. (벽에서 벗어나면 ❌)
• 한 구역을 여러 번 칠해도 상관 없다.
• 다시 칠해야 할 구역은 적어도 한 번은 색칠해줘야 한다.

 

🎯 목표

• 페인트칠을 하는 횟수를 최소화하여 구해야 한다.

 

💌 입력

• n: 벽의 전체 길이
• m: 롤러의 길이 (한 번에 칠할 수 있는 구간의 칸 수)
• section[ ]: 다시 칠해야 하는 구역의 번호 목록 (오름차순, 중복 없음)

 

🔎 예시

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

• 칠해야 할 곳: 2번, 3번, 6번
• 롤러 길이: 4m (즉, 한 번에 연속된 4개의 칸을 칠할 수 있음)

 

• 먼저 3~6번을 칠하면, 3번과 6번이 해결되고, 2번만 남는다.
• 다음으로 1~4번을 칠하면 2번도 해결된다.
• 즉, 최소 횟수는 2번이다.

 

---

💡 아이디어

🧠 핵심 전략

• 마킹 단게
  • 길이 n인 boolean 배열 not_painted[ ]을 만들어준다.
  • 다시 칠해야 하는 구역만 true로 표시해준다.

boolean[] not_painted = new boolean[n];        
for(int s : section){
    not_painted[s - 1] = true;
}

 

• 색칠 단계
  • i = 0부터 n-1까지 훑으면서
    • 만약 not_painted[i] == true라면, 여기서 롤러를 한 번 칠해준다.
    • 이때, [i, i + m - 1] 구간을 전부 false로 바꿔서 덧칠을 해줬음을 표시해준다.
    • 이후, 칠한 횟수 answer를 +1 해준다.

for(int i = 0; i < n; i++){
    if(not_painted[i]){
        answer++;
        
        for(int j = 0; j < m && i + j < n; j++){
            not_painted[i + j] = false;
        }
    }
}

 

 

 

🔎 위의 방법이 최소가 되는 이유

• 왼쪽부터 탐색
  • 벽을 왼쪽에서부터 차례대로 보다가, 처음으로 페인트가 벗겨진 칸 i를 발견했다고 하자.
  • 이 칸은 언젠가는 반드시 칠해줘야 할 것이다.
  • 그런데 그냥 지나가버리면, 나중에 또 돌아와서 i를 포함한 구간을 칠해야 하므로 횟수가 늘어난다.
• 바로 그 자리에서 롤러를 칠하는 이유
  • i에서 롤러를 시작하면, [i ~ (i + m - 1)] 구간을 한 번에 칠할 수 있다.
  • 이 구간 안에 앞으로 칠해야 할 칸이 여럿 들어있을 가능성이 크고,
    그렇다면 한 번에 여러 개의 색칠되지 않은 칸을 해결할 수 있다.
  • 즉, 같은 칸을 두 번 이상 덮을 위험 없이, 가장 멀리 오른쪽까지 덮는 것이 최적인 것이다.
• 과정을 반복하면 최소 횟수 보장
  • 이미 덮인 칸은 다시 볼 필요가 없으므로, 다음 색칠되지 않은 칸에서 다시 롤러를 시작하면 된다.
  • 이렇게 하면 중복 없이 필요한 지점에서만 롤러를 쓰게 되고,
    불필요한 색칠 횟수를 줄여서 항상 최소 횟수를 달성할 수 있다.

 

---

👩🏻‍💻 최종 코드

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        
        boolean[] not_painted = new boolean[n];        
        for(int s : section){
            not_painted[s - 1] = true;
        }
        
        for(int i = 0; i < n; i++){
            if(not_painted[i]){
                answer++;
                    
                for(int j = 0; j < m && i + j < n; j++){
                    not_painted[i + j] = false;
                }
            }
        }      
        
        return answer;
    }
}

 

---

🕑 시간 복잡도

1️⃣ 다시 칠할 구역 마킹

boolean[] not_painted = new boolean[n];
for (int s : section) {
    not_painted[s - 1] = true;
}

 

section 배열을 한 번 순회하며 필요한 위치만 true로 표시하므로,

이 부분의 시간 복잡도는 O(k) 이다.

(이때 k는 section.length)

 

2️⃣ 롤러로 덮기

for (int i = 0; i < n; i++) {
    if (not_painted[i]) {
        answer++;
        for (int j = 0; j < m && i + j < n; j++) {
            not_painted[i + j] = false;
        }
    }
}

 

바깥 루프는 0 ~ n-1 를 한 번 훑으므로 시간 복잡도가 O(n)이다.

 

안쪽 루프는 롤러를 실제로 칠할 때만 최대 m 칸을 false로 설정하는 것이므로,

롤러가 실행된 횟수를 U라고 두면,

안쪽 루프의 총 작업량은 O(Um)이다

 

최악인 상황은 m=1이거나,

섹션 칸들이 서로 m칸 이상 떨어져 있어서 매번 새로 칠해야 할 때인데,

이 때의 시간 복잡도는 O(km)이 될 것이다.

 

 

 

👉🏻 따라서 최종 시간 복잡도는 O(k) + O(n) + O(Um)이다.

     (이때, n은 벽의 길이, k는 다시 칠해야 하는 구역의 수, m은 롤러의 길이이다.)

 

참고로 최악을 기준으로 정리한 최종 시간 복잡도는 O(n + km)이 될 것이다.

 

 

---

👩🏻‍💻다른 풀이 (커서를 두는 그리디 풀이)

import java.util.*;

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;

        // 커서: 지금까지 칠해진 "마지막 구역 번호" (1-based, 아무것도 안 칠했으니 0부터 시작)
        int paintedEnd = 0;

        for (int pos : section) {
            // 이미 칠해진 범위 안이면 패스
            if (pos <= paintedEnd) continue;

            // pos에서 롤러 한 번: [pos .. pos + m - 1]을 덮는다
            answer++;
            paintedEnd = pos + m - 1;
        }

        return answer;
    }
}

 

• pintedEnd: 지금까지 롤러로 칠해진 마지막 구역 번호를 저장한다.
• 왼쪽부터 보며 pos(다시 칠할 구역)가 paintedEnd 안이면 이미 해결된 것이므로 건너뛴다.
• paintedEnd 밖에서 새 pos를 만나면, 그 자리에서 롤러를 한 번 칠한다.
  (paintedEnd = pos + m - 1 로 바뀐다.)
• 이렇게 하면, 한 번 칠할 때 최대한 오른쪽까지 덮으므로, 중복 없이 최소 횟수가 보장된다.

 

이 방법을 사용하면,
section을 한 번만 순회하기 때문에 시간 복잡도는 O(k)로 단축된다.

(이때 k는 section.length)