[백준] 17298 오큰수

문제 설명

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

17298번: 오큰수

크기가 n인 수열이 주어질 때, 수열의 각 원소에 대해서 오큰수를 구하여라

오큰수는 각 원소의 오른쪽에 있으면서 큰 수 중에서 가장 왼쪽에 있는 수이다

그러한 수가 없는 경우에는 -1이다

 

문제 풀이법

이 문제도 역시 Monotone stack을 사용하면 된다

• 수열을 담을 vector<int> v
• monotone stack을 활용할 stack<int> s;
• 답을 담을 vector<int> ans;

이 3개가 필요하다

 

• 우선 수열을 v에 담는다
• 스택에 대해 내림차순(가장 큰 수가 먼저 들어간다는 뜻)을 해야하기에 수열의 맨 끝부터 연산을 한다
  • 만일 스택이 비어있으면 오큰수가 없으므로 바로 ans에 -1을 넣는다
  • 스택이 비어있지 않다면, 스택이 비지 않거나 스택의 top이 현재 수열의 원소보다 크지 않을 때 까지 pop을 하며 while문을 돈다
  • 다 돌았을 때, 비어있다면 오큰수가 없는 것이므로 ans에 -1을 넣는다
  • 비어있지 않으면 스택의 top이 오큰수이므로 ans에 넣는다
• 연산이 끝나면 ans의 값을 출력한다

 

소스 코드

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

using namespace std;

int main()
{   
    int n;
    cin >> n;
    
    stack<int> s;
    vector<int> v;
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    for (int i = n -1; i >= 0; i--)
    {
        if (!s.empty())
        {
            while (!s.empty())
            {
                if (s.top() > v[i])
                    break;
                s.pop();
            }
            if (s.empty())
                ans[i] = -1;
            else    
                ans[i] = s.top();
        }
        else
            ans[i] = -1;
            
        s.push(v[i]);
    }
    
    for (int i = 0; i < n; i++)
        printf("%d ", ans[i]);

    return 0;
}