17298번 오큰수

문제:www.acmicpc.net/problem/17298

17298번: 오큰수

이 문제에서 막힌 부분은 시간초과 였다. 쇠막대기 문제와 비슷한 이유였다. 최악의 경우 시간복잡도 문제가 N^2이 나오기 때문이다. 아래의 코드는 시간초과로 틀렸던 코드이다.

 

#include<iostream>
#include<vector>
#include<cmath>
#include<stack>
#include<deque>
using namespace std;
 
int main()
{
    int vol;
    cin >> vol;
    deque<int> val;
    deque<int> container;
    int tmp;
    for (int i = 0; i < vol; i++)
    {
        cin >> tmp;
        val.push_back(tmp);
    }
    for (int i = 0; i < vol; i++)
    {
        int look = val.front();
        val.pop_front();
        while (val.size()>0&&look >= val.front())
        {
            container.push_back(val.front());
            val.pop_front();
        }
        if (val.size() != 0)
        {
            cout << val.front() << " ";
        }
        else
        {
            cout << -1 << " ";
        }
        auto it = val.insert(val.begin(), container.begin(), container.end());
        container = deque<int>();
        
    }
}

이 문제의 접근법은 Stack의 활용에 있다. 접근 방법은 처음 원소는 비교할 대상이 없으니 우선 스택에 push하고 다음 차례부터는 스택의 top의 위치에 해당하는 값이 지금 차례의 값보다 처음으로 작을때 그 값을 저장하고 확인된 스택 값을 pop하는 형식이다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
 
int main(int argc, char *argv[]) 
{ 
    int n; 
    int num;
    vector<int> v;
    stack<int> s;
 
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        v.push_back(num);
    }
    
    vector<int> ans(v.size(), -1); 
 
    for (int i = 0; i < v.size(); i++) { 
        while (!s.empty() && v[s.top()] < v[i]) { 
            ans[s.top()] = v[i]; 
            s.pop(); 
        } 
        s.push(i); 
    } 
 
    for (int x : ans) {
        cout << x << " ";
    }
    
    return 0;
}

위의 코드는 다음 블로그에서 참고했다.

j3sung.tistory.com/241

[C++] 백준 17298번 오큰수