BOJ 11003 최소값 찾기

이 문제는 처음에는 segment tree를 이용해야 하는 건가 생각했는데, 문제 분류를 보니 sliding window라고 되어있었고 그 걸 보고 나서 좀 감탄을 했다.
L이 정해져있기 때문에 L만큼의 window를 옆으로 이동해나가면서 최소값을 새로 나오는 수와 비교하면서 갱신하고 출력하면 될 것 같아보인다. 왜 sliding window를 생각 못했을까...
그리고 slack에서 본 것인데, 이렇게 sliding window를 쓸 수 있는 것은 L이 고정되어 있기 때문인 것 같다.

출처 : Baekjoon Online Judge Slack

그리고 입력이 500만 개이고, 이 정도 입력으로 입력만으로 1초 이상이 걸린다는 것도 알았다. 예전에 k번째 수 였나...? 그 문제도 입력이 500만이라 입력 시간때문에 nlogn으로는 힘들었던 것 같다.

일단 이 문제도 풀어봐야겠다.
음 풀려고 하니까 문제점이 드러났다. 이게 최소값 정보만 가지고 있고 만약 그 최소값이 그 구간에서 맨 처음 값이라면 window를 한 칸 움직이면 이제 그 구간에서의 최소값이 무엇인지 모른다...
일단 질문 게시판을 참조해보기로 했다. priority_queue를 이용한다는 정보...
그리고 검색으로 블로그 등을 찾아보니 min heap을 이용하는데 deque를 이용했단 글도 보이고...  nlogn으로 푸는 것 같다.

그럼 한 번 segment tree나 fenwick tree를 이용해볼까... fenwick tree로 최소값을 구하는 것도 본 것 같은데 한 번 찾아봐야겠다. 일단 나중에 풀어야겠다.