[백준] 2493 탑 C++

문제 요약

현재 탑의 크기보다 큰 탑 중 왼쪽으로 가장 가까운 탑찾기

접근

1. 생각의 흐름(Greedy)

출력

• 아무것도 없을때 0
• 값이 있으면 해당 인덱스 값 출력 -> (value, index ) 같이 넣어야할듯
  • 저장한 값보다 값이 크면 큰값이 나올때까지 pop
  • 저장한 값보다 값이 작으면 push

전체 코드

#include <iostream>
#include <stack>

#define MAX_N 500000
using namespace std;


int N;
int arr[MAX_N];

int main()
{
    cin >> N;
    for (size_t i = 0; i < N; i++)
        cin >> arr[i];

    stack<pair<int,int>> s; // value, index

    for (size_t i = 0; i < N; i++)
    {
        if (s.empty())
        {
            cout << "0 ";
            s.push({arr[i], i});
        }
        else
        {
            if (s.top().first > arr[i])
            {
                cout << s.top().second + 1 << " ";
                s.push({arr[i], i});
                continue;
            }
            while (!s.empty() && s.top().first < arr[i])
            {
                s.pop();
            }
            if (s.empty())
            {
                cout << "0 ";
            }
            else
            {
                cout << s.top().second + 1 << " ";
            }
            s.push({arr[i], i});
        }
    }
    cout << endl;
    return 0;
}