[알고리즘] 백준 17298

백준 17298번 오큰수

해결 과정 요약

먼저 입력값의 최댓값을 보고 단순 for문으로만 풀 수 있는 문제인지 확인한다.
1000000 * 1000000 는 1조 이므로 O(N^2)인 이중for문 으로는 시간초과가 날 것이다.
고민해본 결과 스택을 이용해서 지나온 값들을 저장해두고 저장한 값들보다 큰 값이 입력으로 주어지면
pop을 반복하는 것이 해법이라는 것을 알게 되었다. 스택으로만 풀 수 있지만 나는 덱을 이용해 앞뒤에서 pop을 해 보았다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N;
int A[1000004];
int ret[1000004];
deque<int> dq;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    fill(ret, ret+1000004, -1);
    
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> A[i];
        while(!dq.empty()){
            if(A[dq.front()] < A[i]){
                ret[dq.front()] = A[i];
                dq.pop_front();
            }
            else if(A[dq.back()] < A[i]){
                ret[dq.back()] = A[i];
                dq.pop_back();
            }
            else break;
        }
        dq.push_back(i);
    }
    for(int i=0; i<N; i++){
        cout << ret[i] << " ";
    }
    return 0;
}

코멘트

자료구조를 떠올리기 어려운 문제.
덱을 활용허면 스택을 사용했을 때보다 시간을 두 배 이상 줄일 수 있다.
deque: 216ms
stack: 680ms