[백준문제풀이] 11003 최솟값 찾기 java 풀이

접근법 : 

**1) 어떻게 풀 것인가?**

이 문제는 덱으로 풀어야한다!! 

**2) 시간복잡도**

2.4초로, 원래 나는 이 문제를 계속 큐로 풀었다가 시간초과가 났다.

나중에 덱으로 해야한다는 사실을 알게되었을 때도.. 오기가 생겨 큐로 계속 도전했었다..ㅋㅋㅋ 하지만 곧 한계를 깨닫고 덱을 쓰기 시작했다!

**3) 공간복잡도**

512mb로 공간은 넉넉한편인것같다

**4) 풀면서 놓쳤던점**

덱을 사용해야한다는 점!

여러 형태의 자료구조에 대해 더 공부해야겠다. 

**5) 이 문제를 통해 얻어갈 것**

덱이라는 아이를 아주 뼈저리게 경험하게되었다.

import java.util.*;
import java.io.*;
public class Main{
static class idx {
public int id;
public int val;
idx(int id, int val) {
this.id = id;
this.val = val;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int n = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
Deque<idx>dequeue = new ArrayDeque();

//썼으니까 다시 만들기
st = new StringTokenizer(br.readLine());

for(int i=0; i<n;i++){
int temp = Integer.parseInt(st.nextToken());
//dequeue가 비어있지 않으며 dequeue의 마지막 값이 새로 들어올 값보다 클 때
if(!dequeue.isEmpty()&& dequeue.getFirst().id < i-l+1){
dequeue.removeFirst();
}
while(!dequeue.isEmpty() && dequeue.getLast().val >= temp){
dequeue.removeLast(); //마지막 원소 삭제
}
dequeue.addLast(new idx(i,temp));
bw.write(dequeue.getFirst().val+" ");
}
bw.flush();
bw.close();
}
}