BAEKJOON 11003번: 최솟값 찾기

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

11003번: 최솟값 찾기

N이 5e6이하로 매우 크다. O(N)짜리 풀이가 필요하다.

조금 생각해보면, deque을 이용해서 범위 밖에 있는 수는 없애주면 되고, 현재 수보다 큰 수는 이제 비교할 필요가 없으므로 없애주면 된다.

 

아래는 코드이다.

우선순위 큐로 푼 사람도 꽤나 있을 것 같은데, 조금만 생각해서 이 풀이대로 해결하면 코딩하는데 1분도 채 안걸린다.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
deque<pii>dq;
int main(){
    int N,L,A;
    scanf("%d%d",&N,&L);
    for(int i=1;i<=N;i++){
        scanf("%d",&A);
        if(i>L&&dq.front().second==i-L)dq.pop_front();
        while(!dq.empty()&&dq.back().first>A)dq.pop_back();
        dq.push_back(pii(A,i));
        printf("%d ",dq.front().first);
    }
    return 0;
}