Skip to main content

[Java] 161989 덧칠하기

📝 덧칠하기

image.png

1. 문제 요약

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

조건

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

2. 접근방법

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

하지만 내가 푼 것처럼 굳이 모든 칸을 관리할 필요가 없고, 어디까지 칠했는지 위치만 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

4. 오답 / 어려웠던 점

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]) {
                for (int j = 0; j < n - 3; j++) {
                    painted[j] = false;
                }
                answer++;
            }
        }
        
        return answer;
    }
}

image.png

1. 내부 for문 범위 틀림

for (int j = 0; j < n - 3; j++) {
    painted[j] = false;
}

i번째부터 m칸 칠한 부분을 false로 바꿔야 하는데, 처음 쓴 코드는 무조건 0 ~ n - 3까지 false 처리하고 있어서 틀림

for (int j = i; j < i + m && j < n; j++) painted[j] = false;

→ 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;
    }
}



Back to top