[백준 2493] 탑

www.acmicpc.net/problem/2493

2493번: 탑

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

골5였지만 구현은 단순했다. 이전 문제와 마찬가지로 거꾸로 배열을 돌면서 현재값 < 스택의 탑이라면 push, 현재값 > 스택의 탑이라면 pop을 한다.

#include <stdio.h>
#include <stack>

using namespace std;

int n;
int arr[500000];
int res[500000];
stack<int> s;
int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  s.push(n - 1);

  for (int i = n - 2; i > -1; i--)
  {

    if (arr[s.top()] > arr[i])
    {
      s.push(i);
    }
    else
    {
      while (!s.empty() && arr[s.top()] < arr[i])
      {
        res[s.top()] = i + 1;
        s.pop();
      }
      s.push(i);
    }
  }
  for (int i = 0; i < n; i++)
  {
    printf("%d ", res[i]);
  }
  return 0;
}