[JAVA/Deque] 백준 11003 최솟값 찾기

1. 문제

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

11003번: 최솟값 찾기

 

2. 풀이

    방법 1) 우선 순위 큐 사용

자바로 우선 순위 큐를 사용해 정렬 된 값을 바로 사용해서 하려고 했더니 시간 초과가 난다. 자바로 풀기 위해 다른 방법을 찾아 봤다.

    방법 2) Deque 사용

숫자가 있는 위치와 숫자의 값을 모두 Deque에 넣어 풀이하는 방법이다. 

    (1) 현재 숫자를 입력 받는다.

    (2) 현재 덱 내에 있는 수 중 뒤에서 부터 자기보다 작은 값을 만나기 전까지 pop_back을 반복한다.

        (덱 내 있는 수 중 자기보다 작은 값 == 현재 위치에서의 min 후보이므로)

    (3) Deque에 현재 숫자와 그 숫자의 위치를 넣는다.

    +) (1) ~ (3)의 과정을 통해 Deque가 오름차순으로 유지된다.

    (4) Deque의 가장 앞에 있는 수가 범위에 걸리면(front[1] == i - L) pop_front

    (5) 현재 Deque의 가장 앞에 있는 수가 지금까지의 min 값이므로 StringBuilder에 추가한다.

    (6) (1) ~ (5)의 과정을 숫자 입력 받는 동안 반복한다.

 

+) 주의점

시간이 매우 짧다보니 자바로 했을 때 제약점이 많은 것 같다. 

BufferedReader, BufferedWriter, StringBuilder을 모두 써야 시간 내 통과가 됐다.

 

3. 코드

 

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

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());
        
        Deque<int[]> dq = new ArrayDeque<>(); // 숫자 값, 인덱스
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0; i < N; i++) {
            int now = Integer.parseInt(st.nextToken()); 
            // 현재 입력받은 수보다 작은 수를 만나기 전까지 pop_back 
            while(!dq.isEmpty()) {
                int[] n = dq.getLast(); 
                if(n[0] >= now) // 덱의 맨 마지막에 있는 숫자가 현재 입력받은 숫자보다 크면
                    dq.pollLast();  // 덱에서 제거
                else break;
            }
            dq.addLast(new int[] {now, i}); // 현재 입력 받은 수 추가
            if(dq.getFirst()[1] == i - L) { // 범위에 걸리는 경우
                dq.pollFirst(); // pop
            }
            int[] front = dq.getFirst(); 
            sb.append(front[0] + " "); 
            
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    
    }
}