[백준] 11003 최소값 찾기 java

1. 문제 설명

문제 링크

2. 접근 방식

슬라이딩 윈도우와 자료구조 덱큐를 이용한다.

해당 문제는 데이터의 개수가 이미 10^6이라서 O(n) 안에 문제를 해결 해야한다. 이 문제를 윈도우 안에 있는 값들을 최소값 정렬해서 풀려는 사람들이 있을지 모르는데, 정렬은 O(nlogn)이 들어서 시간초과가 난다.
따라서 덱을 이용해 정렬의 효과를 내야한다. 덱큐의 조건은 다음과 같다.

1. 현재 바라보고 있는 값을 덱큐에 넣을 예정이다.

   (1) 만약 덱큐의 꼬리의 있는 값보다 현재 넣으려고 하는 값이 작으면 꼬리에 있는 값을 제거한다.
   (2) 어짜피 슬라이딩 윈도우 기준 제일 오른쪽에 있는 값이 더 작다면 그것보다 왼쪽에 있는 값이 클 경우, 쓸모가 없다. 어짜피 슬리이딩 윈도우가 이동하는 내내, 현재 원소보다 상대적으로 왼쪽에 있는 값들이 최소값으로 쓰일 일이 없기 때문이다.

2. 현재 바라보고 있는 값을 넣으므로써, 슬라이딩 윈도우 영역을 벗어나는 값은 삭제한다.

이를 위해서는 값마다 자신의 index와 value를 가지고 있어야 한다. Node라는 클래스를 만들어서 이를 저장해서 진행한다.

3. 코드 분석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {

    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        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());

        ArrayDeque<Node> aq1 = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            Node now = new Node(i, Integer.parseInt(st.nextToken()));

            if(aq1.isEmpty()) aq1.add(now);
            else{
                if(now.idx - L > 0 && aq1.getFirst().idx <= now.idx - L) aq1.poll();

                while(!aq1.isEmpty() && aq1.getLast().v > now.v){
                    aq1.pollLast();
                }

                aq1.add(now);
            }

            sb.append(aq1.getFirst().v).append(" ");
        }

        System.out.println(sb);

    }
}

class Node {
    int idx;
    int v;

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