백준 17298 : 오큰수

링크 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

가장 쉬운 방법은 for loop을 두 개 써서 O(n^2)의 시간 복잡도로 푸는 것입니다. 하지만 N이 최대 1,000,000까지 될 수 있기 때문에 당연히 시간 초과가 뜰 것입니다. 스택을 이용한다면 O(n)의 시간 복잡도로 풀 수 있습니다. 이렇게 모든 원소에 대해 원소 오른쪽/왼쪽에 어떤 조건을 만족하는 첫번째 원소를 구하라는 문제는 보통 단일 스택 (monotonic stack, 상황에 따라 deque도 사용하기도 함) 을 사용하면 O(n)의 시간 복잡도로 풀 수 있습니다. 모든 원소가 스택에 push가 한번씩 되고, pop이 한번씩 되기 때문에 O(n)의 시간 복잡도를 지닙니다. 단일 스택 (monotonic stack)에 대해서는 차후 포스팅에서 자세하게 한번 다뤄보겠습니다.

 

코드

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cstdio>
#include <stack>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    
    stack<int> st;
    vector<int> ans(v.size(), -1);
    for (int i = 0; i < v.size(); i++) {
    	while (!st.empty() && v[st.top()] < v[i] ) {
    		ans[st.top()] = v[i];
    		st.pop();
    	}
    	st.push(i);
    }
    for (int x : ans) cout << x << " ";
    return 0;
}