백준 11003 : 최솟값 찾기

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

11003번: 최솟값 찾기

[ 문제풀이 ]

처음에는 세그먼트 트리를 사용하였는데 TLE가 발생하였다. 이 문제는 덱(Deque) 자료구조를 활용하면 해결할 수 있는 문제이다.

1부터 N까지 순차적으로 탐색하면서 덱을 항상 L개 이하의 크기를 유지하면서 제일 첫 번째 원소는 범위에서 가장 작은 값을 가지도록 구현해주면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static class Node {
        int pos, v;

        public Node(int pos, int v) {
            this.pos = pos;
            this.v = v;
        }
    }

    static int N, L;
    static Node[] node;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());
            node = new Node[N + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; ++i) {
                node[i] = new Node(i, Integer.parseInt(st.nextToken()));
            }

            Deque<Node> deque = new ArrayDeque<>();
            for (int i = 1; i <= N; ++i) {
            	//덱의 마지막 원소가 현재 node[i]의 v값보다 크면 최솟값이 아니기 때문에 제거
                while (!deque.isEmpty() && deque.peekLast().v > node[i].v) {
                    deque.pollLast();
                }
                //현재 node 삽입
                deque.addLast(node[i]);
                //덱의 첫번째원소부터 현재 구간에 속하지 않는 node 제거
                while (!deque.isEmpty() && deque.peekFirst().pos < i - L + 1) {
                    deque.pollFirst();
                }
                bw.write(deque.peekFirst().v + " ");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}