[JAVA][백준][P5] 11003번 최솟값 찾기

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

 

📒 문제

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

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

 

● 시간 제한 / 메모리 제한

 2.4 초 / 512 MB 

 

입력

첫째 줄에 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

 

알고리즘 분류

• 자료 구조
• 우선순위 큐
• 덱
• 덱을 이용한 구간 최댓값 트릭

---

💻 소스코드

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

public class Main{
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 풀이 시작
        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> mydeque = new LinkedList<>();
        for(int i = 0 ; i < N ; i ++){
            int now =  Integer.parseInt(st.nextToken());

            while(!mydeque.isEmpty() && mydeque.getLast().value > now){
                mydeque.removeLast();
            }

            mydeque.addLast(new Node(now,i));

            if(mydeque.getFirst().index <= i-L){
                mydeque.removeFirst();
            }

            bw.write(mydeque.getFirst().value + " ");
        }

        bw.flush();
        bw.close();
    }
    
}

class Node{
    public int value;
    public int index;

    public Node(int value, int index){
        this.value = value;
        this.index = index;
    }
}

📝 풀이

해당 문제는 덱을 슬라이딩 윈도우와 덱을 이용해서 문제를 해결 하였다.

 

덱(deque)은 Double-Ended Queue의 줄임말로, 선입선출 구조의 큐(Queue)와 다르게 앞뒤로 넣고 빼고 가능한 구조로 되어있다.

 

그래서 덱 구조에 값과 인덱스로 구성된 노드를 한개씩 계산하면서 정렬 알고리즘을 사용하지 않고 문제를 해결할 수 있었다.

 

새로운 노드가 뒤로 들어오면 뒤에서 부터 새로운 노드 보다 값이 크면 제거하고 아니면 덱에 새로운 노드를 집어 넣는다, 그리고 가장 앞 노드의 인덱스를 이용해 범위 L만큼의 노드가 덱에 들어있는지 계산 후 젤 앞의 노드의 값을 출력하여 값을 구했다.

 

입출력의 예시의 흐름을 차례로 보면 아래처럼 확인 가능하다.

 

[ 0, 1 ] 
addLast : [ 0, 1 ] 

[ 1, 5 ] 
addLast : [ 0, 1 ] [ 1, 5 ] 

[ 2, 2 ] 
removeLast : [ 0, 1 ] 
addLast : [ 0, 1 ] [ 2, 2 ] 

[ 3, 3 ] 
addLast : [ 0, 1 ] [ 2, 2 ] [ 3, 3 ] 
removeFirst : [ 2, 2 ] [ 3, 3 ] 

[ 4, 6 ] 
addLast : [ 2, 2 ] [ 3, 3 ] [ 4, 6 ] 

[ 5, 2 ] 
removeLast : [ 2, 2 ] [ 3, 3 ] 
removeLast : [ 2, 2 ] 
addLast : [ 2, 2 ] [ 5, 2 ] 
removeFirst : [ 5, 2 ] 

[ 6, 3 ] 
addLast : [ 5, 2 ] [ 6, 3 ] 

[ 7, 7 ] 
addLast : [ 5, 2 ] [ 6, 3 ] [ 7, 7 ] 

[ 8, 3 ] 
removeLast : [ 5, 2 ] [ 6, 3 ] 
addLast : [ 5, 2 ] [ 6, 3 ] [ 8, 3 ] 
removeFirst : [ 6, 3 ] [ 8, 3 ] 

[ 9, 5 ] 
addLast : [ 6, 3 ] [ 8, 3 ] [ 9, 5 ] 
removeFirst : [ 8, 3 ] [ 9, 5 ] 

[ 10, 2 ] 
removeLast : [ 8, 3 ] 
removeLast : 
addLast : [ 10, 2 ] 

[ 11, 6 ] 
addLast : [ 10, 2 ] [ 11, 6 ]