BOJ11003: 최솟값 찾기

작성일

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

  • 1월동안 100문제 풀기 (13/100)
  • LC에서 풀어본 덱문제. 문제가 거의 완전히 똑같은것 같다.
  • 당시에 이 문제의 답을 보고도 이해하기가 엄청나게 힘들었는데,
  • 지금은 그냥 바로 해법이 생각나고 이해가 되었다.
  • 포인트는 왜 현재 보고있는 값보다 덱의 back이 클 경우는 그냥 버려도 되는지 이해하는것
  • C++로도 2초를 꽉채우기 때문에.. Python으로는 불가능할듯.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int N, L, cur;
struct Node {
  int val, pos;
};

int main() {
  scanf("%d %d", &N,&L);

  deque<Node> dq;
  for(int i = 0; i < N; i++) {
    scanf("%d", &cur);
    while(dq.size() && dq.back().val > cur)
      dq.pop_back();
    if(dq.size() && i - dq.front().pos == L)
      dq.pop_front();
    dq.push_back({cur,i});
    printf("%d ", dq.front().val);
  }
}