[Java] 백준 11003. 최솟값 찾기

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

 

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

 

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

 

예제 입력 1

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 1

1 1 1 2 2 2 2 2 3 3 2 2

 

 

풀이

슬라이딩 윈도우 알고리즘을 사용했다.

연속된 L개의 숫자 중 최솟값을 출력하는 문제인데 정렬을 하지 않고 값을 비교하면서 데크에 넣어주면서 loop가 한 번 끝날 때마다 데크의 제일 처음 값만 출력해주도록 했다.

1. 만약 데크의 마지막 노드 값이 현재 값보다 클 경우 마지막 값이 현재 값보다 작을 때까지 혹은 데크가 빌 때까지 마지막 노드를 제거한다.
2. 현재 값을 데크의 마지막 노드로 추가한다.
3. 만약 데크의 첫번째 노드 인덱스가 마지막 인덱스 - L 보다 작거나 같다면 제거한다.
4. 데크의 첫 번째 값을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Node {
    public int index;
    public int value;

    public Node(int index, int value) {
        this.index = index;
        this.value = value;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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> deque = new LinkedList<>();

        for(int i=0; i<n; i++) {
            int current = Integer.parseInt(st.nextToken());
            while(!deque.isEmpty() && deque.getLast().value > current) {
                deque.removeLast();
            }
            deque.addLast(new Node(i, current));

            if(deque.getFirst().index <= i-l) {
                deque.removeFirst();
            }
            sb.append(deque.getFirst().value).append(" ");
        }

        System.out.println(sb.toString());
    }
}