문제 요약
m x n 크기의 사막 격자가 주어진다.
이 격자 안에 세로 h, 가로 w 크기의 선인장 구역을 하나 정해야 한다.
선인장 구역은 격자 축에 맞춘 연속된 직사각형이다.
비는 drops 배열에 주어진 순서대로 격자의 칸에 떨어진다.
선인장 구역 안에 포함된 칸 중 하나라도 처음 비를 맞는 순간이 해당 선인장 구역이 처음 비를 맞는 시각이다.
목표는 다음 조건을 만족하는 선인장 구역의 왼쪽 위 좌표를 구하는 것이다.
- 가능한 한 늦게 비를 맞는 구역을 선택한다.
- 아예 비를 맞지 않는 구역이 있다면 그 구역이 가장 우선이다.
- 후보가 여러 개라면 가장 위쪽 행을 선택한다.
- 그래도 여러 개라면 가장 왼쪽 열을 선택한다.
핵심 아이디어
각 칸에 비가 떨어지는 시각을 숫자로 적어보자.
예를 들어 어떤 칸이 첫 번째로 비를 맞으면 1, 두 번째로 비를 맞으면 2를 저장한다.
비가 끝까지 오지 않는 칸은 아주 큰 값인 INF로 둔다.
그러면 어떤 h x w 선인장 구역이 처음 비를 맞는 시각은 다음과 같다.
그 직사각형 안에 있는 칸들의 비 시각 중 최솟값왜냐하면 직사각형 안에서 가장 먼저 비를 맞는 칸이 곧 선인장 구역이 처음 비를 맞는 순간이기 때문이다.
따라서 문제는 다음과 같이 바뀐다.
모든
h x w부분 직사각형의 최솟값을 구하고, 그 최솟값이 가장 큰 직사각형을 찾기
이는 2차원 슬라이딩 윈도우 최솟값으로 해결할 수 있다.
비 시각 배열 만들기
먼저 모든 칸을 INF로 초기화한다.
INF = len(drops) + 1
rain_time = [INF] * (m * n)drops에 등장하는 칸은 순서대로 시각을 기록한다.
for time, (row, col) in enumerate(drops, 1):
rain_time[row * n + col] = timeINF를 len(drops) + 1로 둔 이유는 모든 실제 비 시각보다 크기 때문이다.
따라서 비를 맞지 않는 칸이 포함된 경우 자연스럽게 더 늦은 시각으로 처리된다.
만약 어떤 선인장 구역 안의 모든 칸이 INF라면, 그 구역은 끝까지 비를 맞지 않는 구역이다.
2차원 최솟값을 바로 구하면?
모든 위치마다 h x w 영역을 직접 확인하면 시간이 너무 오래 걸린다.
가능한 선인장 구역의 개수는 대략 다음과 같다.
(m - h + 1) x (n - w + 1)각 구역마다 h x w칸을 모두 확인하면 최악의 경우 비효율적이다.
그래서 행 방향과 열 방향으로 나누어 최솟값을 구한다.
1단계: 각 행에서 가로 w칸의 최솟값 구하기
먼저 각 행에 대해 연속된 w칸의 최솟값을 구한다.
예를 들어 한 행이 다음과 같고 w = 3이라고 하자.
[5, 2, 7, 4, 6]가로 길이 3인 구간의 최솟값은 다음과 같다.
[5, 2, 7] -> 2
[2, 7, 4] -> 2
[7, 4, 6] -> 4결과:
[2, 2, 4]이 값을 모든 행에 대해 구하면 m x (n - w + 1) 크기의 배열이 만들어진다.
2단계: 세로 h칸의 최솟값 구하기
1단계에서 만든 배열에 대해 이번에는 각 열마다 연속된 h칸의 최솟값을 구한다.
그러면 각 h x w 직사각형의 최솟값을 얻을 수 있다.
즉, 다음 순서로 처리한다.
원본 격자
-> 행마다 가로 w칸 최솟값
-> 열마다 세로 h칸 최솟값
-> 모든 h x w 직사각형의 최솟값덱을 이용한 슬라이딩 윈도우 최솟값
연속 구간 최솟값은 덱을 사용하면 O(원소 개수)에 구할 수 있다.
덱에는 값이 작은 원소가 앞에 오도록 인덱스를 저장한다.
새 값을 넣을 때는 뒤에서부터 현재 값보다 크거나 같은 값을 제거한다.
while dq and arr[dq[-1]] >= arr[current]:
dq.pop()그리고 현재 인덱스를 넣는다.
dq.append(current)윈도우 범위를 벗어난 인덱스는 앞에서 제거한다.
if dq[0] <= current - window_size:
dq.popleft()그러면 덱의 맨 앞에는 항상 현재 윈도우의 최솟값 인덱스가 있다.
동률 처리
조건은 다음과 같다.
- 가장 늦게 비를 맞는 구역
- 가장 위쪽
- 가장 왼쪽
직사각형을 위쪽 행부터, 같은 행에서는 왼쪽 열부터 확인하면 된다.
그리고 더 좋은 값이 나왔을 때만 정답을 갱신한다.
if value > best:
best = value
answer = [row, col]동일한 값일 때 갱신하지 않으면 먼저 발견한 위치가 유지된다.
따라서 자연스럽게 가장 위쪽, 가장 왼쪽 좌표가 선택된다.
전체 코드
from collections import deque
def solution(m, n, h, w, drops):
INF = len(drops) + 1
rain_time = [INF] * (m * n)
for time, (row, col) in enumerate(drops, 1):
rain_time[row * n + col] = time
row_window_count = n - w + 1
row_min = [0] * (m * row_window_count)
for row in range(m):
dq = deque()
row_start = row * n
output_start = row * row_window_count
for col in range(n):
current = row_start + col
while dq and rain_time[dq[-1]] >= rain_time[current]:
dq.pop()
dq.append(current)
if dq[0] <= row_start + col - w:
dq.popleft()
if col >= w - 1:
output_col = col - w + 1
row_min[output_start + output_col] = rain_time[dq[0]]
best = -1
answer = [0, 0]
for col in range(row_window_count):
dq = deque()
for row in range(m):
current = row * row_window_count + col
while dq and row_min[dq[-1]] >= row_min[current]:
dq.pop()
dq.append(current)
if dq[0] <= (row - h) * row_window_count + col:
dq.popleft()
if row >= h - 1:
top_row = row - h + 1
value = row_min[dq[0]]
if value > best:
best = value
answer = [top_row, col]
return answer코드 설명
1차원 배열을 사용한 이유
m x n <= 500,000이므로 전체 칸 수는 크지 않다.
하지만 m이나 n 중 하나는 매우 클 수 있다.
예를 들어 다음과 같은 경우가 가능하다.
m = 500000
n = 1이때 2차원 리스트를 만들면 작은 리스트가 너무 많이 생긴다.
그래서 내부적으로는 1차원 배열을 사용한다.
좌표 (row, col)은 다음 인덱스로 변환한다.
index = row * n + col비를 맞지 않는 구역 처리
비가 오지 않는 칸은 INF 값을 가진다.
어떤 선인장 구역의 모든 칸이 INF라면 그 구역의 최솟값도 INF다.
이는 실제 비 시각보다 항상 크므로, 비를 맞지 않는 구역이 자동으로 가장 우선 선택된다.
예시
다음과 같은 격자를 생각해보자.
m = 2
n = 2
h = 1
w = 1
drops = [[0, 0], [0, 1], [1, 0]]비 시각 배열은 다음과 같다.
1 2
3 INF1 x 1 구역을 선택하므로 각 칸이 그대로 후보가 된다.
가장 늦게 비를 맞는 칸은 INF인 (1, 1)이다.
결과:
[1, 1]또 다른 예시
m = 2
n = 2
h = 2
w = 1
drops = [[0, 0], [1, 1]]비 시각 배열:
1 INF
INF 2가능한 선인장 구역은 두 개다.
왼쪽 열
1
INF처음 비를 맞는 시각은 1이다.
오른쪽 열
INF
2처음 비를 맞는 시각은 2이다.
따라서 오른쪽 열을 선택한다.
결과:
[0, 1]시간 복잡도
전체 칸 수를 K = m x n이라고 하자.
각 행에서 가로 슬라이딩 윈도우를 한 번 수행한다.
O(K)그 결과 배열에 대해 각 열에서 세로 슬라이딩 윈도우를 한 번 수행한다.
O(K)따라서 전체 시간 복잡도는 다음과 같다.
O(m x n)제한사항에서 다음 조건을 만족한다.
m x n <= 500,000따라서 충분히 처리할 수 있다.
공간 복잡도
비 시각 배열과 가로 최솟값 배열을 저장한다.
O(m x n)정리
이 문제는 선인장 구역이 처음 비를 맞는 시각을 어떻게 계산할지가 핵심이다.
어떤 구역이 처음 비를 맞는 시각은 그 구역 안의 칸들 중 가장 작은 비 시각이다.
따라서 모든 h x w 직사각형의 최솟값을 빠르게 구하면 된다.
풀이 흐름은 다음과 같다.
- 각 칸에 비가 떨어지는 시각을 기록한다.
- 비가 오지 않는 칸은
INF로 둔다. - 각 행에서 가로
w칸 최솟값을 구한다. - 그 결과에 대해 각 열에서 세로
h칸 최솟값을 구한다. - 가장 큰 최솟값을 가진 구역을 선택한다.
- 동률이면 먼저 탐색한 위쪽, 왼쪽 좌표를 유지한다.
2차원 구간 최솟값을 행과 열의 두 번의 슬라이딩 윈도우로 나누는 것이 핵심이다.
