[Algorithm] boj_11003 자료구조 활용

문제

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

접근 방법

조건

1. 순차적으로 탐색하며 최솟값을 갱신해야 한다.

2. 범위가 크기 때문에, O(N)의 탐색 방법을 찾아야한다.

접근

• Deque로 구간 관리 (idx를 저장)

• 요소가 들어올때마다

  1. 범위를 벗어난 idx가 존재할경우 모두 삭제
  2. 현재 요소보다 큰 값은 모두 삭제(어차피 최소가 될 수 없음) 후, 마지막에 넣는다.

하지만, 여기서 O(N)의 조건을 충족해야하기 때문에, deque.remove(idx);로 요소를 지우면 안된다.

2번 동작에서 어차피 새로운 요소보다 큰 요소는 모두 삭제하고 마지막에 offer 하기때문에, 덱은 arr[idx] 기준으로 오름차순 정렬되어있다. 따라서 pollFirst()로 (O(1)를 충족) 지워주면 된다.

결국 덱을 이용해서 삽입/삭제가 모두 가장 앞/뒤에서만 일어나서 O(1)을 충족시킬 수 있다.

코드

package basic.algorithm.baekjoon.dataStructure;

import java.io.*;
import java.util.*;

public class boj_11003_deque { //다시 풀어보기

    static int N, L;
    static int[] arr;
    static int[] min;
    static Deque<Integer> deque;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        deque = new ArrayDeque<>();
        arr = new int[N];
        min = new int[N];

        //input arr
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        deque.offerFirst(0);
        sb.append(arr[0]).append(" ");

        //구간 탐색
        for (int i = 1; i < N; i++) {

            //범위를 벗어난 요소 인덱스 제거
            while (!deque.isEmpty() && deque.peekFirst() < i - L + 1) {
                deque.pollFirst();
            }

            //뒤에서부터(큰값부터) 현재 요소보다 큰 값은 모두 지운다.
            while (!deque.isEmpty() && arr[deque.peekLast()] > arr[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            sb.append(arr[deque.peekFirst()]).append(" ");
        }

        System.out.println(sb);
    }
}