프로그래머스 선인장 숨기기 풀이: 2차원 슬라이딩 윈도우
작성·코드 검증: solve together · 작성 언어: Python
0. 문제 링크와 출처
- 문제: 선인장 숨기기
- 출처: 프로그래머스, 2025 카카오 하반기 2차
- 자체 판단 난이도: Level 4
각 h × w 구역의 최솟값을 구하는 문제를 2차원 슬라이딩 윈도우로 바꾸고, 가로와 세로에
단조 덱을 연속 적용해야 한다. 최대 500,000칸의 입력에서 O(mn)을 유지해야 하므로
자료구조 선택과 최적화 발상의 진입 장벽이 높아 Level 4로 판단했다.
1. 문제 요약
m × n 격자에 세로 h, 가로 w 크기의 선인장 구역을 배치하려고 한다. 빗방울은 drops 배열의 순서대로 격자에 떨어진다.
선인장 구역 안의 칸 중 하나라도 비를 맞으면 그 시점에 선인장이 젖는다. 따라서 어떤 구역이 처음 젖는 시점은 그 구역에 포함된 칸들의 첫 강수 시점 중 최솟값이다.
다음 우선순위로 선인장 구역의 왼쪽 위 좌표를 선택한다.
- 가능한 한 늦게 처음 비를 맞는 구역
- 끝까지 비를 맞지 않는 구역
- 같은 시점이면 가장 위쪽 행
- 그래도 같으면 가장 왼쪽 열
격자 전체 크기는 최대 500,000칸이지만, 구역 하나를 매번 직접 검사하면 비효율적이다. 각 h × w 직사각형의 최솟값을 빠르게 구하는 것이 핵심이다.
2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명
구간 판정
drops[i] = [r, c]는 해당 칸에 i + 1번째로 비가 내린다는 뜻이다. 먼저 다음과 같은 rain_time 배열을 만든다.
- 비가 내린 칸: 실제 강수 순서
1 ~ len(drops) - 비가 내리지 않은 칸:
INF = len(drops) + 1
구역 안의 최솟값이 클수록 늦게 젖고, 최솟값이 INF이면 끝까지 젖지 않는 구역이다.
1차 슬라이딩 윈도우: 가로 방향
각 행에서 길이 w인 구간의 최솟값을 구한다. 이 값을 row_min에 저장하면 row_min[r][c]는 (r, c)에서 시작하는 가로 구간의 최솟값이 된다.
윈도우가 오른쪽으로 한 칸 이동할 때마다 새로 들어온 값만 확인하면 되지만, 최솟값이 빠져나가는 경우도 처리해야 한다. 이를 위해 덱에 최솟값 후보의 인덱스를 오름차순으로 유지한다.
- 현재 값보다 크거나 같은 덱 뒤쪽 값은 최솟값 후보가 아니므로 제거한다.
- 윈도우 왼쪽을 벗어난 덱 앞쪽 인덱스를 제거한다.
- 덱의 앞쪽 인덱스가 현재 윈도우의 최솟값이다.
2차 슬라이딩 윈도우: 세로 방향
가로 방향 최솟값을 구한 결과에 같은 작업을 열 단위로 적용한다. 높이 h인 세로 윈도우의 최솟값은 결국 해당 h × w 직사각형 전체의 최솟값이다.
세로 윈도우에서 얻은 값이 해당 구역의 첫 강수 시점이다. 모든 열을 왼쪽부터, 각 열의 시작 행을 위부터 순회하며 더 좋은 후보를 갱신한다. 단, 탐색 순서만으로는 행 우선순위가 보장되지 않으므로 강수 시점이 같을 때 (행, 열)을 직접 비교한다.
복잡도
각 칸은 가로 슬라이딩 윈도우와 세로 슬라이딩 윈도우에서 각각 덱에 한 번 들어가고 한 번 나온다. 따라서 시간 복잡도는 O(m × n), 공간 복잡도는 O(m × n)이다.
m × n ≤ 500,000이므로 이 복잡도는 제한 조건 안에서 동작할 수 있다.
직사각형 최솟값으로 바꾸는 이유
직사각형이 처음 젖는 시점은 내부 칸들의 강수 시점 중 최솟값이다. 각 칸을 강수 순서라는 숫자로 바꾸면 문제는 고정 크기 직사각형 최솟값 문제가 된다. 가로 구간 최솟값을 먼저 구하고 그 결과에 세로 구간 최솟값을 적용하면 2차원 문제를 두 번의 선형 스캔으로 나눌 수 있다.
오답 접근과 반례
직사각형 안에 내린 마지막 비의 시점을 사용하면 처음 젖는 시점을 구할 수 없다. 내부 강수 시점이 [2, 9]인 구역은 9번째 비가 아니라 2번째 비에 이미 젖는다. 이 문제에서는 합이나 최댓값이 아니라 최솟값을 비교해야 한다.
3. 문제 해결 코드 (Python)
from collections import deque
def solution(m, n, h, w, drops):
inf = len(drops) + 1
# 각 칸이 처음 비를 맞는 순서를 저장한다.
rain_time = [inf] * (m * n)
for order, (row, col) in enumerate(drops, start=1):
rain_time[row * n + col] = order
window_width = n - w + 1
row_min = [inf] * (m * window_width)
# 각 행에서 길이 w인 구간의 최솟값을 계산한다.
for row in range(m):
queue = deque()
row_start = row * n
result_start = row * window_width
for col in range(n):
value = rain_time[row_start + col]
while queue and rain_time[row_start + queue[-1]] >= value:
queue.pop()
queue.append(col)
while queue and queue[0] <= col - w:
queue.popleft()
if col >= w - 1:
row_min[result_start + col - w + 1] = rain_time[row_start + queue[0]]
best_time = -1
answer = [0, 0]
# 각 열에서 높이 h인 구간의 최솟값을 계산한다.
for col in range(window_width):
queue = deque()
for row in range(m):
value = row_min[row * window_width + col]
while queue and row_min[queue[-1] * window_width + col] >= value:
queue.pop()
queue.append(row)
while queue and queue[0] <= row - h:
queue.popleft()
if row >= h - 1:
top = row - h + 1
first_rain = row_min[queue[0] * window_width + col]
if first_rain > best_time or (
first_rain == best_time and (top, col) < tuple(answer)
):
best_time = first_rain
answer = [top, col]
return answer구현 포인트
INF를 사용해 비가 한 번도 내리지 않은 구역을 가장 늦은 후보로 처리한다.- 모든 배열을 2차원 리스트 대신 평탄화된 1차원 리스트로 저장해 큰 행·열 한쪽이 500,000에 가까운 경우에도 불필요한 리스트 객체를 줄인다.
- 덱에는 현재 윈도우에서 최솟값이 될 가능성이 있는 인덱스만 남긴다.
- 같은 강수 시점이라면
(top, col)이 작은 후보를 선택한다. - 입력
drops가 비가 내리는 순서이므로 별도의 정렬이 필요하지 않다.
복사해 실행할 테스트
아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 젖지 않은 구역이 가장 늦은 후보가 되는 경우를 확인할 수 있다.
assert solution(1, 2, 1, 1, [[0, 0]]) == [0, 1]
assert solution(1, 1, 1, 1, [[0, 0]]) == [0, 0]4. 참고 풀이 비교
- 99doldol의 Python 풀이는 각 칸의 강수 순서를 기록한 뒤 가로와 세로에 슬라이딩 윈도우를 두 번 적용하는 방식을 설명한다.
접근 방법은 크게 두 가지다. 누적합은 특정 영역의 합을 빠르게 구하는 데 강하지만, 이 문제는 직사각형 내부의 최솟값이 필요하므로 단순 누적합만으로는 해결할 수 없다. 이 글에서는 단조 덱을 이용해 최솟값을 유지하는 2차원 슬라이딩 윈도우를 선택했다.
마무리
이 문제의 핵심은 선인장 구역을 하나씩 검사하는 것이 아니라, 먼저 각 칸의 강수 시점을 숫자로 바꾸고 모든 고정 크기 직사각형의 최솟값을 효율적으로 계산하는 것이다. 행 방향과 열 방향에 슬라이딩 윈도우를 차례로 적용하면 최대 500,000칸의 격자도 선형 시간에 처리할 수 있다.