📑 1. 문제설명



1. 문제 요약
- 벽 길이 = n (1m 단위 구역으로 나눔, 번호 1~n)
- 롤러 길이 = m (한 번 칠하면 연속 m칸이 칠해짐)
- 반드시 다시 칠해야 하는 구역 = section 배열
조건
- 롤러는 벽 밖으로 나가면 안 됨
- 구역은 부분만 칠할 수 없음. (롤러 시작 위치는 항상 구역 경계에 맞춰야 함)
- 이미 칠한 구역은 다시 칠해도 됨
- section에 포함된 구역은 최소 한 번은 칠해야 함
- 최소 롤러 사용횟수 리턴
💡 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;
}
}
- 처음에는 마지막으로 칠해진 구간 끝 위치를 0으로 잡기
- section을 순회하면서 s > paintedEnd라면 answer++
- 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
'코딩테스트 > JAVA테스트' 카테고리의 다른 글
| [프로그래머스] (Java) 삼총사 문제풀이 - 완전탐색, 투포인터 (1) | 2025.09.03 |
|---|---|
| [프로그래머스] (Java) 서울에서 김서방 찾기 (1) | 2025.09.03 |
| [프로그래머스] (Java) 2016년 (1) | 2025.09.03 |
| [프로그래머스] (Java) 영어 끝말잇기 문제풀이 - 해시 HashSet (5) | 2025.08.30 |
| [프로그래머스] (Java) 괄호 회전하기 문제풀이 - 스택 (4) | 2025.08.30 |