[c/c++] 백준 17298

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

17298번: 오큰수

 

접근 방식

이중 for문을 통해 답을 구해보려 했지만, n <= 1,000,000이기 때문에 O(n^2)인 방법으로 풀게 되면 시간 초과가 나게 된다.

 

풀이 방법

stack을 이용하여 접근해보았다.

stack은 오큰수가 될 수 있는 수를 저장하는 역할이다. (stack이 비어있다면 오큰수가 없다는 뜻이다.) 

vector를 역순으로 탐색하면서 stack에 있는 수를 검사한다.

stack은 vector를 탐색하며 while(vector[i]>=stack.top()) stack.pop()하는 식으로 관리된다. vector[i]>=stack.top()이라면 stack.top()은 vector[i]보다 크지도 않고, vector[i]보다 오른쪽에 있지도 않으므로 오큰수가 될 수 없다.

n-1부터 0까지 탐색하는 i에 대해 stack을 관리하며 ans[i]를 채워주고 stack에 vector[i]를 넣어주는 과정을 반복해주면 된다. 이렇게 하면 O(n)의 시간복잡도로 답을 구할 수 있다.

 

코드

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int> v;
    vector<int> ans;
    stack<int> st;
    
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        v.push_back(x);
        ans.push_back(0);
    }
    
    for(int i=n-1;i>=0;i--){
        while(!st.empty()&&st.top()<=v[i]) st.pop(); //stack이 비어있는지 확인
        
        if(st.empty()) ans[i]=-1;
        else ans[i]=st.top();
        
        st.push(v[i]);
    }
    
    for(int i=0;i<n;i++) cout<<ans[i]<<' ';
    
    return 0;
}