BOJ 17298 - 오큰수

www.acmicpc.net/problem/17298

17298번: 오큰수

 

N 의 최대 크기가 백만이기 때문에, 단순히 이중 포문을 쓰면 당연히 시간초과가 발생한다

그래서, 처음에 N 개의 수들을 벡터에 저장해 둔 뒤, 스택을 이용해서 풀어야 한다

(사실 스택을 쓰는것을, 문제에서 주는 힌트를 보고 스택써야겠구나 생각했다)

 

스택에는, N개의 수가 들어가는게 아니라, N개의 수가 위치한 인덱스 값을 넣는다

비어있는 상태의 스택에서는, 즉 첫번째 인덱스는 반드시 들어가고

스택이 비어있지 않은 상태에서는, 스택의 top 에 담긴 인덱스에 해당하는 수와 다음 차례에 해당하는 수 끼리 비교해서 다음 차례가 더 크다는것은, 오른쪽에 있는 수가 더 크다는 의미가 되므로 조건을 만족하는 상태가 된다

따라서 이때, 답을 갱신해주고, 스택에서 하나씩 빼준다. 

이런식으로 처리를 해주면 답이 나오게 된다.

 

- c++

#include <bits/stdc++.h>
 
using namespace std;
 
int N;
vector<int> vec;
stack<int> st;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        vec.push_back(num);
    }
    
    vector<int> answer(vec.size(), -1);
    
    for (int i = 0; i < vec.size(); ++i) {
        while(!st.empty() && vec[st.top()] < vec[i]) {
            answer[st.top()] = vec[i];
            st.pop();
        }
        st.push(i);
    }
    
    for (int i = 0; i < answer.size(); ++i) {
        cout << answer[i] << " ";
    }
    
    return 0;
}