[백준] 11003번 최솟값 찾기

문제 설명

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

문제 풀이

• 데크 자료구조를 이용하여 풀이하였다.
• 데크의 구조는 아래와 같다.

  deque<Integer, Integer> : 데크에 (인덱스, 값) 형태로 저장
  deque[0] : 구간 내 최소값 저장
  deque[i] (i > 0) : 구간 내 최소값 후보들 저장

• 각 숫자들을 입력 받으면서 수행하는 로직은 다음과 같다.

  1. 데크의 맨 앞값(최소값)이 현재 필요한 범위를 벗어날 경우 빼줌.
  2. 현재값을 데크의 뒤에 넣되 현재값보다 큰 값들을 뒤에서 모두 빼줌

• 위 로직에서 2번이 의미하는 것은 데크의 앞쪽에서 뒤쪽까지 인덱스는 증가하는 형태가 되며, 현재값보다 값이 크되 이전에 있는 인덱스의 정보들은 이후 탐색에서 최소값 후보로써, 최소값으로써 의미가 없어지기 때문에 모두 빼주는 것이다.

소스 코드 (JAVA)

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

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;

    public static class Point {
        int ind, v;

        public Point(int ind, int v) {
            this.ind = ind;
            this.v = v;
        }
    }

    public static int N, M;

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    }

    public static void solve() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
         Deque<Point> dq = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            //1. 데크의 맨 앞값(최소값)이 인덱스 넘어서면 빼줌
            if (!dq.isEmpty() && dq.getFirst().ind < i - M + 1) dq.pollFirst();
            //2. 현재값을 뒤에 넣되 현재값보다 큰 값들 뒤에서 모두 빼줌
            if (!dq.isEmpty()) {
                while(true) {
                    if (dq.isEmpty()) break;
                    if (dq.getLast().v >= num) dq.pollLast();
                    else break;
                }
            }
            dq.addLast(new Point(i, num));
            bw.write(dq.getFirst().v + " ");
        }
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}