[BOJ] 오큰수_17298 C++ 풀이

문제

크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

접근 방법

Ai의 오른쪽에 있으면서 Ai 보다 큰 수 중에 가장 왼쪽 값을 구하는 문제이므로 스택을 사용하여 접근해 보았다. 먼저 N개의 수를 스택 st1에 입력 받았고 st1의 top에 위치하는 값을 오큰수 비교를 위한 스택 st2에 삽입해 주었다. 오큰수가 존재 하지 않기 때문에 -1을 result스택에 push 해주었고 st1의 top 원소를 삭제 하였다.

그 후 st1 스택이 빈 상태가 될때 까지 st1 top의 값을 st2 스택의 top의 값과 비교해 가며 result 스택에 값을 삽입해 주었다.

st2에 삽입될 st1의 top 값이 기존 st2의 top값 보다 크거나 같다면 st2의 top 값이 st1의 top값보다 클때까지 st2의 원소를 삭제해 준다. 이때 st2가 빈 상태가 되었다면 st1의 top값 보다 오큰수가 없다는 뜻이므로 -1을 result 스택에 삽입해 주고, st2에 st1 top 보다 큰값이 존재한다면 그 값이 st1 top의 오큰수 이므로 st2의 top을 result 스택에 삽입해 준다.

구현

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

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,a;
    stack<int> st1, st2;
    stack<int> result;

    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a;
        st1.push(a);
    }

    st2.push(st1.top());
    result.push(-1);
    st1.pop();

    while(!st1.empty())
    {
        while(st2.top()<=st1.top())
        {
            st2.pop();
            if(st2.empty()) break;
        }
        if(st2.empty()) result.push(-1);
        else result.push(st2.top());
        st2.push(st1.top());
        st1.pop();
    }

    while(!result.empty())
    {
        cout<<result.top()<<' ';
        result.pop();
    }
    return 0;
}

BOJ_오큰수