프로그래머스 선인장 숨기기 풀이: 2차원 슬라이딩 윈도우
작성자: solve together · 작성 언어: Python
0. 문제 링크와 출처
- 문제: 선인장 숨기기
- 출처: 프로그래머스, 2025 카카오 하반기 2차
- 자체 판단 난이도: 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가 비가 내리는 순서이므로 별도의 정렬이 필요하지 않습니다.
4. 동일한 문제를 어떻게 풀었나 웹검색 하여 요약
공개된 풀이들은 모두 모든 직사각형을 직접 순회하는 방식의 시간복잡도 문제를 해결하기 위해, 각 칸의 강수 시점을 저장한 뒤 직사각형 최솟값을 빠르게 계산하는 방향으로 접근합니다.
- 프로그래머스 공식 문제 페이지는 선인장 구역이 처음 비를 맞는 시점을 구역 내부 강수 시점의 최솟값으로 판단할 수 있는 조건과, 늦은 시점·행·열 순서의 우선순위를 제시합니다.
- 99doldol의 Python 풀이는 각 칸의 강수 순서를 기록한 뒤 가로와 세로에 슬라이딩 윈도우를 두 번 적용하는 방식을 설명합니다.
접근 방법은 크게 두 가지입니다. 누적합은 특정 영역의 합을 빠르게 구하는 데 강하지만, 이 문제는 직사각형 내부의 최솟값이 필요하므로 단순 누적합만으로는 해결할 수 없습니다. 이 글에서는 단조 덱을 이용해 최솟값을 유지하는 2차원 슬라이딩 윈도우를 선택했습니다.
마무리
이 문제의 핵심은 선인장 구역을 하나씩 검사하는 것이 아니라, 먼저 각 칸의 강수 시점을 숫자로 바꾸고 모든 고정 크기 직사각형의 최솟값을 효율적으로 계산하는 것입니다. 행 방향과 열 방향에 슬라이딩 윈도우를 차례로 적용하면 최대 500,000칸의 격자도 선형 시간에 처리할 수 있습니다.