[백준]BOJ11003-최솟값 찾기

문제내용

---

많은 포스트를 봤고, 슬라이딩윈도우와 Deque를 사용해서 풀어야 하는지 '문제풀이' 에 대한 글이 없어서 남겨 보고자한다.

 

개인적으로 국어능력이 너무 부족해서 내가 문제를 이해하는게 너무 힘들었어서 내가 알아보기 위해서 기록으로 남겨놓고자 한다.

 

제한시간의 경우 2.4초,Java기준 2.6초이며 N의 범위가 5,000,000까지 가기 때문에 정렬인 nlogn을 사용하는 순간 시간을 넘겨버린다. 따라서 O(N)을 사용해야 한다.

---

첫째줄에는 N과 L이 주어진다.

N의 경우에는 숫자가 주어질 총 갯수이며 L의 경우에는 슬라이딩 윈도우의 범위이다.

 

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력 이 말이 잘 이해가 되지를 않았었으나 풀어보자면

 

1 5 2 3 6 2 3 이 있을때 2번쨰 인덱스가 5인 경우 3~5의 인덱스 중에 최솟값을 구해야 한다는 말이다...

즉 2 3 6 중에서 최솟값은 2가 되는것

---

 

Reference : http://www.yes24.com/Product/Goods/108571508