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

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

해당 문제는 'Do it! 알고리즘 코딩테스트 자바 편'을 보면서 공부한 내용입니다.

👉 문제

일정 범위 안에서 최솟값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용하면 될 것 같다고 합니다..

우선, 여기서 쓰이는 슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만 부분 배열의 길이(크기)가 고정적입니다. 어떤 창문을 왼쪽부터 오른쪽으로 밀어 오면서 창문(윈도우) 안에 있는 값들을 부분 배열이라고 생각하면 될 것 같습니다. 

슬라이딩 윈도우를 덱(Deque)으로 구현하여 정렬 효과를 볼 수 있습니다.

참고로, 윈도우의 크기 는 문제에서 최솟값을 구하는 범위가 i-L+1부터 i까지 이므로 L로 생각하면 됩니다. (예제에서는 3)

<풀이 이해>

1. 덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장합니다.
   (1,1)
   (1,1) - (2,5)

2. 위 상태에서 새 노드 (3,2)가 덱에 저장됩니다. 여기부터 기존 덱에 있던 노드가 제거됩니다.
   (1,1) - (2,5) <- (3,2)

   뒤에서부터 비교하여 값이 5>2 이므로 (2,5) 노드를 제거하고 1<2 이므로 탐색을 멈춘 후 다음과 같이 바뀝니다.
   (1,1) - (3,2)

   정리 후 덱의 인덱스 범위는 1~3이므로 최솟값을 찾아도 됩니다. 이미 정렬이 되있는 상태이기 때문에 최솟값 찾기는 쉽습니다. 바로 처음에 있는 (1,1) 노드입니다.

3. 계속해서 입력받는 새 노드를 추가합니다. 이번에는 인덱스 범위가 슬라이딩 윈도우를 벗어난 예시를 볼 수 있습니다.
   (1,1) - (3,2) <- (4,3)

   2<3 이므로 탐색을 멈추지만, 4(마지막 데이터 index) - 3(슬라이딩 윈도우 크기) >= 1 이므로 맨 앞 데이터는 슬라이딩 윈도우 크기를 벗어나 삭제합니다. 제거가 끝난 이후에 최솟값을 출력하면 2입니다.

4. 최종적으로 숫자 비교, 윈도우 범위 계산이 끝난 덱에서 맨 앞에 있는 노드의 숫자값을 출력하기만 하면 정답이 됩니다.

👉 풀이

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

public class _11003_1 {
    public static final Scanner sc = new Scanner(System.in);

    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());

        st = new StringTokenizer(br.readLine());
        Deque<Node> mydeque = new LinkedList<>();
        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();
    }

    static class Node {
        public int value;
        public int index;

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

👉 성능