[백준 17298] 오큰수

www.acmicpc.net/problem/17298

17298번: 오큰수

스택을 사용하는 문제이다.

입력받은 배열을 거꾸로 돌면서 스택의 탑에 위치한 값이 현재 배열 값보다 작다면 팝한다. 

만약 스택이 비어있다면 -> 현재값보다 큰 값이 오른쪽에 위치하지 않았다는 의미이므로 -1을 푸쉬한다.

먄약 스택이 비어있지 않다면 -> 스택의 탑값을 결과값에 푸쉬한다. 탑에 있는게 가장 왼쪽에 있는 값이기 때문이다.

 

그리고 항상 마지막엔 현재 값을 푸쉬해준다. 

//오큰수 오른쪽에 있으면서 a보다 큰 수 중 가장 왼쪽에 있는 수
#include <stdio.h>
#include <stack>
using namespace std;

int arr[1000001];
stack<int> st;
stack<int> res;
int main(void)
{
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  for (int i = n - 1; i > -1; i--)
  {
    int cur = arr[i];
    while (!st.empty() && st.top() <= cur)
    {
      st.pop();
    }

    if (st.empty())
    {
      res.push(-1);
    }
    else
    {
      res.push(st.top());
    }

    st.push(cur);
  }

  while (!res.empty())
  {
    printf("%d ", res.top());
    res.pop();
  }

  return 0;
}