[프로그래머스] 2025 카카오 하반기 2차 선인장 숨기기 - Python

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/468379

프로그래머스

 

아이디어

---

이 문제는 m * n 격자에서 크기 h * w인 직사각형 구역 하나를 골라,

그 구역이 처음으로 비를 맞는 시점이 최대가 되도록 하는 문제이다.

 

처음에는 모든 h * w 구역을 직접 확인하면서, 그 안에 포함된 칸들 중 가장 먼저 젖는 시간을 구하는 

브루트포스로 문제를 해결하고자 했다.

 

하지만, 문제 제한사항에서 m, n, h, w의 최대값이 아래처럼 주어져있고

 

브루트포스의 시간 복잡도가 O(m * n * h * w)이기 때문에, 시간초과가 날 것이라 판단했다.

 

이에 

1. 각 칸이 몇 번째 빗방울에 처음 젖는지 기록 (안젖는 칸은 INF 값으로 채우기)

2. [a,b]를 시작으로 하는 h * w 직사각형 내부 값 중 최소값 기록

3. 기록된 2차원 배열 중 최대값 찾기

 

이렇게 생각해보면,

 

2차원 배열에서 모든 h * w 크기 직사각형 내부의 최소값을 빠르게 찾는 것

 

으로 문제를 바꾸어 생각해볼 수 있다.

 

이때 가장 많이 사용하는 것이 슬라이딩 윈도우 알고리즘이다.

 

 

슬라이딩 윈도우

---

슬라이딩 윈도우 알고리즘은 

 

고정된 크기의 창(윈도우)을 데이터 배열 위에서 한 칸씩 이동시키면서 필요한 계산을 수행하는 방식이다.

 

위 문제와는 다르지만, 

 

배열 [3,1,4,1,5,9,2] 에서 크기가 3인 창(k = 3)을 사용하여 각 단계의 '창 내부 합계'를 구하는 과정을 예시로 들어보면

 

1단계. 초기 윈도우 설정 (첫 번째 합계 계산)

이미지 1: 배열 [3, 1, 4, 1, 5, 9, 2]에서 k=3인 첫 번째 윈도우 [3, 1, 4]의 합계 8을 계산하는 장면

 

배열의 가장 왼쪽(인덱스 0)부터 시작하여 창의 크기(k = 3)만큼 데이터를 선택한다.

첫 번째 창은 위 그림처럼 [3,1,4]를 포함하여, 이 세 숫자의 합인 8을 계산한다.

 

2단계. 슬라이드 시작 (첫 번째 요소 제거 및 새 요소 추가)

이미지 2: 윈도우가 오른쪽으로 이동하며 '3'이 제거되고 '1'이 추가됨. 합계가 8에서 6으로 업데이트되는 과정

 

윈도우가 오른쪽으로 한 칸 이동한다. 

1. 기존 윈도우의 왼쪽 요소인 3(인덱스 0)이 윈도우 밖으로 이동한다.

2. 새로운 요소인 1(인덱스 3)이 윈도우 안으로 들어온다.

3. 기존 합계인 8에서 새로 들어온 1을 더하고, 제거된 3을 뺀 6을 업데이트한다.

 

3단계. 연속적인 슬라이드 및 업데이트 

이미지 3: 윈도우가 다시 이동하여 '1'이 제거되고 '5'가 추가됨. 합계가 6에서 10으로 업데이트됨

 

윈도우가 다시 오른쪽으로 한 칸 슬라이드한다.

1. 이전 윈도우의 왼쪽 요소인 1 제거

2. 새로운 요소인 5 추가

 

이때, 내부 값은 기억할 필요 없이 이전 합계에서 나간 값과 들어온 값만 적용해 계산한다.

 

4단계. 마지막 윈도우 및 최종 결과

이미지 4: 윈도우가 마지막 위치 [5, 9, 2]에 도달하여 합계 16을 계산함. 모든 윈도우의 합계들이 저장되고 최종 결과가 도출됨

 

윈도우가 마지막 위치에 도달한다. (슬라이드 완료)

1. 이전 윈도우의 가장 왼쪽 요소인 1을 제거, 2 추가.

 

이렇게 전체 배열에 대한 계산이 완료되면,

각 단계에서 구한 윈도우의 합계들 (Window Sums [8,6,10,15,16] ) 중 가장 큰 값인 16이 최종 결과로 도출

 

이 슬라이딩 윈도우 알고리즘을 적용해 문제를 해결하였다.

 

전체 코드

---

'''
W*H 격자를 (0,0)부터 이동
격자 내 최소값 계산해서 저장

브루트포스 -> 너무 커짐 O(n*m*h*w)

데이터 전처리
1. w * 1 크기의 슬라이드 만들기
2. 한칸씩 밀면서 최소값 찾기
3. 모든 열 반복 -> 배열에 저장

=> m * (n - w + 1) 크기의 배열 생성

4. 1 * h 크기의 슬라이드 만들기
5. 한칸씩 밀면서 최소값 찾기
6. 모든 열 반복 -> 배열에 저장

7. 배열 중 최대값 출력
'''

from collections import deque

def solution(m, n, h, w, drops):
    answer = []
    INF = len(drops) + 1 #끝까지 비 안맞는 칸 (최대값)
    
    # 각 칸이 몇번째에 젖는지 기록
    time = [[INF] * n for _ in range(m)]
    for i in range(len(drops)):
        a, b = drops[i]
        time[a][b] = i + 1
    
    width = n - w + 1
    row_min = [[0] * width for _ in range(m)]
    
    for i in range(m):
        dq = deque() # 최소값 인덱스 저장
        for j in range(n):
            # 덱 맨 뒤 값이 현재 값보다 크거나 같으면 제거 (최소값만 덱에 저장하기 위해) 
            while dq and time[i][dq[-1]] >= time[i][j]:
                dq.pop()
            
            dq.append(j)
            
            # 슬라이드 범위 밖 인덱스 제거
            while dq and dq[0] <= j - w:
                dq.popleft()
            
            # 길이 w가 완성되면서부터 최소값 기록
            if j >= w - 1:
                row_min[i][j - w + 1] = time[i][dq[0]]

    
    #row_min 배열에서 한번 더 슬라이드-윈도우 -> rect_min에 저장
    height = m - h + 1
    rect_min = [[0] * width for _ in range(height)]
    for j in range(width):
        dq = deque()
        for i in range(m):
            while dq and row_min[dq[-1]][j] >= row_min[i][j]:
                dq.pop()
            
            dq.append(i)
            
            while dq and dq[0] <= i - h:
                dq.popleft()
            
            if i >= h - 1:
                rect_min[i - h + 1][j] = row_min[dq[0]][j]
    
    maxValue = -1
    answer = [0, 0]
    
    # 정답 탐색
    for i in range(height):
        for j in range(width):
            if rect_min[i][j] > maxValue:
                maxValue = rect_min[i][j]
                answer = [i, j]
            
    return answer

 

1. 각 칸이 언제 젖는지 기록 (데이터 전처리)

INF = len(drops) + 1
time = [[INF] * n for _ in range(m)]

for i in range(len(drops)):
    a, b = drops[i]
    time[a][b] = i + 1

 

문제에서 drops[i] 는 i + 1 번째로 비가 떨어지는 좌표를 의미한다.

 

그래서 time[a][b] 를 그 칸이 몇 번째 빗방울에서 젖는지로 정의할 수 있다.

 

비가 한 번도 떨어지지 않은 칸은 끝까지 안젖는 칸이므로,

가장 큰 값인 len(drops) + 1 로 설정했다.

 

이렇게 하면 특정 직사각형 안의 최소값이 곧 

그 구역이 처음 비를 맞는 시점이 된다.

 

2. 가로 길이 w 최소값 구하기

width = n - w + 1
row_min = [[0] * width for _ in range(m)]

 

먼저 각 행에 대해 길이 w짜리 구간의 최소값을 삽입할 배열을 만든다.

 

3. 덱으로 1차 슬라이딩 윈도우 최소값 처리

for i in range(m):
    dq = deque()
    for j in range(n):
        while dq and time[i][dq[-1]] >= time[i][j]:
            dq.pop()
        
        dq.append(j)
        
        while dq and dq[0] <= j - w:
            dq.popleft()
        
        if j >= w - 1:
            row_min[i][j - w + 1] = time[i][dq[0]]

 

이 부분은 1차원 슬라이딩 윈도우 최소값의 전형적인 형태이다.

 

덱에는 현재 윈도우 안에서 최소값 후보가 되는 인덱스들만 남긴다.

 

• 뒤에서부터 현재 값보다 크거나 같은 값 제거 (최소값 후보만 남기기 위해)
• 현재 인덱스 추가
• 윈도우 범위를 벗어난 앞쪽 인덱스 제거
• 덱의 맨 앞부터 최소값 배열에 추가

 

4. 세로 길이 h 최소값 구하기

height = m - h + 1
rect_min = [[0] * width for _ in range(height)]

 

이제 row_min 배열을 기준으로, 

각 열마다 높이 h 짜리 구간의 최소 값을 한번 더 구한다.

 

그러면 최종적으로 rect_min[i][j]는 

왼쪽 위가 (i,j)인 h * w 직사각형 안의 최소값이 된다.

 

5. 덱으로 2차 슬라이딩 윈도우 최소값 처리

for j in range(width):
    dq = deque()
    for i in range(m):
        while dq and row_min[dq[-1]][j] >= row_min[i][j]:
            dq.pop()
        
        dq.append(i)
        
        while dq and dq[0] <= i - h:
            dq.popleft()
        
        if i >= h - 1:
            rect_min[i - h + 1][j] = row_min[dq[0]][j]

 

이번에는 행이 아니라 열 방향으로 같은 작업을 반복한다. 

 

이렇게 하면, 브루트포스처럼 직사각형 내부 순회를 칸마다 반복할 필요가 없다.

 

6. 최대값이 되는 위치 찾기

maxValue = -1
answer = [0, 0]

for i in range(height):
    for j in range(width):
        if rect_min[i][j] > maxValue:
            maxValue = rect_min[i][j]
            answer = [i, j]

 

이제 rect_min 내부 값 중 최대값의 위치를 고르면 된다.

 

 

 

정리

---

배열에서 특정 범위를 기준으로 작업을 해야 할 땐, 

 

슬라이딩 윈도우 알고리즘을 사용할 수 있게 문제를 다른 시각으로 바라볼 필요가 있다.