[백준] 최솟값 찾기(11003)

https://www.acmicpc.net/problem/11003

$D_i = A_{i - L + 1}$ ~ $A_i$ 중의 최솟값이라는 부분에서 $i-L+1$이 핵심이다.

예제를 기준으로 생각해보자.
N = 12, L = 3
i = 1, 2, 3 ...

$D_1 = A_{1-3+1}$ ~ $A_1$ = $A_{-1}$ ~ $A_1$
=> 최솟값은 1
$D_2 = A_{2-3+1}$ ~ $A_2$ = $A_{0}$ ~ $A_2$
=> 최솟값은 1
$D_3 = A_{3-3+1}$ ~ $A_3$ = $A_{1}$ ~ $A_3$
=> 최솟값은 1
$D_4 = A_{4-3+1}$ ~ $A_4$ = $A_{2}$ ~ $A_4$
=> 최솟값은 2
...

크기가 L인 범위에서 슬라이딩 윈도우 알고리즘을 사용하여 최솟값을 찾으면 될 것 같다는 느낌이 온다.

근데 N과 L의 범위가 최대 5,000,000이다... 데이터 크기가 $O(nlogn)$의 1초당 최대 연산 가능 횟수인 100만을 훌쩍 넘어버린다...

따라서 정렬 알고리즘을 사용할 수 없다.

그래서 양방향으로 넣고 뺄 수 있는 덱(Deque) 자료구조를 사용해서 정렬과 동일한 효과를 볼 수 있도록 구현해야한다.

문제풀이 방법은 다음과 같다.

1. i = 0에서 N까지 반복하면서
   덱의 마지막 요소의 값이 $A_i$의 값보다 클 경우 마지막 요소값 제거

2. $A_i$의 값을 새롭게 덱에 추가

3. 첫번째 요소값이 윈도우 범위 L을 벗어난 경우
   덱의 첫번째 요소값 제거

4. 최소값은 항상 덱의 첫번째 요소값

Python

import sys
input = sys.stdin.readline

# 시간복잡도 O(N)에 해결하기 위해 덱 사용
# 덱은 튜플로 (값, 인덱스) 형태로 저장됨
# e.g. mydeque = [(1, 0), (2, 1), (3, 2)]
from collections import deque

N, L = map(int, input().split())
mydeque = deque() # 비어있는 덱 선언
A = list(map(int, input().split()))

for i in range(N):
    # 마지막 요소의 값이 입력값보다 클 경우
    while mydeque and mydeque[-1][0] > A[i]: # mydeque[-1][0]은 마지막 요소의 값을 들고옴
        mydeque.pop() # 마지막 요소값 제거
    
    # 입력값을 덱에 새롭게 추가
    mydeque.append((A[i], i))

    # 첫번째 요소의 값이 윈도우 범위를 벗어난 경우
    # 첫번째 요소의 인덱스 값과 윈도우 범위를 비교해주면 됨
    # e.g. mydeque[0][1] == 0
    # e.g. i = 3, L = 3, i - L == 0
    if mydeque[0][1] <= i - L:
        mydeque.popleft() # 첫번째 요소값 제거
    
    print(mydeque[0][0], end=' ') # 최소값은 항상 가장 첫번째 요소값

Java

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class P_11003 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 출력을 버퍼에 넣고 한 번에 출력하기 위해 BufferedWriter 사용
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        Deque<Node> mydeque = new LinkedList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int now = Integer.parseInt(st.nextToken());

            // 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거한 후
            while (!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }
            // 가장 마지막 순서로 추가
            mydeque.addLast(new Node(now, i));

            // 슬라이딩 윈도우 범위에서 벗어난 값은 덱에서 제거
            if (mydeque.getFirst().index <= i - L) {
                mydeque.removeFirst();
            }
            // 최소값을 가져와 버퍼에 쓰기
            bw.write(mydeque.getFirst().value + " ");
        }
        
        bw.flush(); // 버퍼를 비워내고 화면에 출력
        bw.close(); // 버퍼 닫아 메모리 해제
    }

    // value, index를 저장하는 Node 클래스
    static class Node {
        public int value;
        public int index;

        public Node(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}

Deque과 메서드에 대한 설명은 아래 링크에 정리해 두었으니 참고하길 바란다.

27. Deque 개념설명: https://velog.io/@wonotter/Java-Basics-5