프로그래머스 LV2 - 선인장 숨기기

작년 하반기 카카오 2차 코테 문제인데, 그때는 못풀었던 것 같다.
해설이 궁금해서 찾아보니, 슬라이딩 윈도우를 가로세로로 각각 적용해서 푸는 문제라고 한다.

슬라이딩 윈도우의 개념만 알고 있었지, 이를 코드로 구현하는데는 자신이 없었던 지라 기본 개념을 코드로 옮기는 방법부터 문제 풀이까지 포스팅 해보려고 한다.

---

1. 슬라이딩 윈도우란?

슬라이딩 윈도우(Sliding Window)는
고정된 크기의 구간(window)을 한 칸씩 이동시키며 값을 계산하는 기법이다.

예를 들어 배열이 다음과 같다고 하자:

[4, 2, 7, 1, 5]

길이 k = 3인 구간을 본다면:

[4, 2, 7]
   [2, 7, 1]
      [7, 1, 5]

이처럼 창(window)을 오른쪽으로 이동시키며 계산한다.

---

왜 필요한가?

각 구간마다 min() 또는 max()를 구하면:

시간복잡도: O(n * k)

n과 k가 클 경우 비효율적이다.

---

deque 기반 슬라이딩 윈도우

슬라이딩 윈도우를 O(n)으로 줄이는 핵심 아이디어는 다음과 같다.

"쓸모 없는 값은 미리 제거한다"

---

슬라이딩 윈도우 핵심 코드 패턴

# 1. 큰 값 제거
while dq and arr[dq[-1]] >= arr[i]:
    dq.pop()

# 2. 현재 값 추가
dq.append(i)

# 3. 범위 밖 제거
if dq[0] <= i - k:
    dq.popleft()
# 4. 앞
if i >= k - 1:
    result.append(arr[dq[0]])

---

직관

deque는 항상 다음과 같은 상태를 유지한다:

앞 → 최소값
뒤 → 큰 값들

작은 값은 오래 살아남고, 큰 값은 제거된다.

---

예시

arr = [4, 2, 7, 1, 5], k=3
결과: [2, 1, 1]

과정:

i	값	deque 상태 (값 기준)	결과
0	4	[4]	-
1	2	[2]	-
2	7	[2, 7]	2
3	1	[1]	1
4	5	[1, 5]	1

---

2. 선인장 숨기기 문제

문제 요약

• m x n 격자
• 비가 떨어지는 순서가 주어짐
• h x w 크기의 직사각형을 놓는다
• 해당 영역에서 가장 먼저 비 맞는 시간 (최솟값)을 구한다
• 그 값이 가장 큰 위치를 찾는다
  

---

핵심 아이디어

직사각형 최소값을 빠르게 구하는 것이 핵심이다.

naive 접근

직사각형마다 전체 탐색 → O(n^3)

최적화 전략

1. 가로 슬라이딩 (w)
2. 세로 슬라이딩 (h)

2차원 문제를 1차원 두 번으로 나눈다.

---

Step 1: rain 배열 생성

rain[r][c] = 해당 칸에 비가 오는 시간

비가 오지 않는 칸은 INF

---

Step 2: 가로 슬라이딩

각 행에서 길이 w 구간의 최소값을 구한다.

예:

[1, INF, INF, INF, 8]
→ [1, INF, INF, 8]

결과를 row_min에 저장한다.

---

Step 3: 세로 슬라이딩

row_min을 기준으로 세로 h 구간의 최소값을 구한다.

---

핵심 직관

직사각형 최소값 = 각 행의 가로 최소값들 중 최소

따라서 가로 → 세로 순서로 계산하면 된다.

---

예제1

m=4, n=5, h=2, w=2

rain 배열

[1, INF, INF, INF, 8]
[INF, 5, INF, 3, INF]
[INF, INF, 6, 7, 4]
[INF, 2, INF, INF, INF]

---

가로 슬라이딩 결과

[1, INF, INF, 8]
[5, 5, 3, 3]
[INF, 6, 6, 4]
[2, 2, INF, INF]

---

세로 슬라이딩 결과

[1, 5, 3, 3]
[5, 5, 3, 3]
[2, 2, 6, 4]

---

최종 결과

가장 큰 값은 6

정답: [2, 2]

---

시간복잡도

가로: O(m * n)
세로: O(m * n)
총: O(m * n)

---

정답 코드

from collections import deque

def solution(m, n, h, w, drops):
    total = m * n
    INF = 999
    
    rain = [INF] * total

    # 2차원 배열을 1차원 배열로 변환
    for i in range(len(drops)):
        r, c = drops[i]
        rain[r * n + c] = i + 1
    print(rain)

    new_n = n - w + 1
    row_min = [0] * (m * new_n)

    # 가로 슬라이딩 윈도우 (row 기준)
    for r in range(m):
        dq = deque()

        for c in range(n):
            while dq and rain[r*n + dq[-1]] >= rain[r*n + c]:
                dq.pop()

            dq.append(c)

            if dq[0] <= c - w:
                dq.popleft()

            if c >= w - 1:
                row_min[r * new_n + (c - w + 1)] = rain[r*n + dq[0]]

    new_m = m - h + 1

    best_time = -1
    best_r = 0
    best_c = 0

    # 세로 슬라이딩 윈도우 (column 기준)
    for c in range(new_n):
        dq = deque()

        for r in range(m):
            val = row_min[r * new_n + c]

            while dq and row_min[dq[-1] * new_n + c] >= val:
                dq.pop()

            dq.append(r)

            if dq[0] <= r - h:
                dq.popleft()

            if r >= h - 1:
                cur = row_min[dq[0] * new_n + c]
                sr = r - h + 1

                if (cur > best_time or
                   (cur == best_time and (sr < best_r or (sr == best_r and c < best_c)))):
                    
                    best_time = cur
                    best_r = sr
                    best_c = c

    return [best_r, best_c]