[백준] 17298.cpp : 오큰수

www.acmicpc.net/problem/17298

17298번: 오큰수

---

• 수열의 크기가 백만이니, 이중 반복문으로 직접 돌리는 방식은 가능하지 않다.
• 현재 위치보다 오른쪽에 있는 수들 중 큰 값을 구하는 것이니, 뒤에서부터 큰 값을 저장해나가며 비교하는 방식을 생각해보자.
• 스택이 비어 있다면(현재 위치보다 큰 값이 없는 상태), 자기 자신을 큰 값으로 넣어주고 답은 -1 을 저장한다.
• 현재 위치보다 스택의 값이 크다면, 스택의 값을 답에 저장하고 다음 위치(앞) 으로 가서 비교한다. 하지만 이후에 나올 수보다는 클 수도 있기 때문에 일단 스택에 저장해놓는다.
• 만약 현재 위치보다 스택의 값이 작다면, 해당 값은 앞으로도 쭉 의미가 없어지기 때문에 지워준다. 위치를 갱신하지 않고, 조건에 걸릴 때까지 반복해준다.

---

#include <iostream>
#include <stack>
using namespace std;

int n;
int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n;
    stack<int> s;                       // 입력값 받을 스택
    stack<int> ans;                     // 답 출력용 스택
    for(int i = 0, data ; i < n ; i++)
    {
        cin >> data;
        s.push(data);
    }

    stack<int> temp;                    // 오른쪽부터 큰 수들을 저장할 스택
    while(!s.empty())                   // 입력값들을 다 처리할때 까지
    {
        if(temp.empty())                // if 나보다 큰 수가 없어서 다 비워졌다면
        {
            ans.push(-1);               // 현재 위치의 답은 -1
            temp.push(s.top());         // 자기 자신을 가장 큰 값으로 스택에 저장
        }
        else                            // else 값이 있을 경우엔
        {
            if(s.top() < temp.top())        // if 그 값이 나보다 클 경우
            {
                ans.push(temp.top());       // 현재 위치의 답이 해당 값
                temp.push(s.top());         // 나보다 앞에 있는 수 보다 내가 클 수도 있으니 일단은 저장
            }
            else                            // else 그 값이 나보다 작을 경우
            {
                temp.pop();                 // 해당 값은 쓸모없어지기 때문에 버리고
                continue;                   // 현재 위치 답 구할때까지 반복
            }
        }
        s.pop();                        // 다음 위치(앞 인덱스)로!
    }

    while(!ans.empty())                 // 답 출력
    {
        cout << ans.top() << " ";
        ans.pop();
    }
    cout << '\n';
}