백준/2493번/탑/골드5

Problem Link: https://www.acmicpc.net/problem/2493

문제 설명

Site: Baekjoon
Number: 2493
Category: Stack
Rank: Gold 5

여러개의 숫자가 주어졌을 때, 자신의 왼쪽 편에 처음으로 자기보다 큰 숫자가 나오는 경우 그 순서를 출력하고, 없다면 0을 출력하는 문제입니다.

문제 풀이

두 개의 스택과 배열 하나를 사용해서 해결하였습니다.

스택 s1은 처음 입력받은 숫자들이며, 스택 s2는 스택 s1에서 하나씩 빼내어 해당 숫자의 높이와 인덱스를 저장하고,

이를 s1의 요소들과 하나씩 비교하여 자기보다 큰 숫자가 나오는 경우 배열의 자기 인덱스에 해당 숫자의 인덱스를 저장합니다.

마지막에 배열을 1~N까지 요소를 출력해주면 됩니다.

#include <iostream>
#include <stack>

using namespace std;

#define PII pair<int, int>

int arr[500001];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N;
    cin >> N;

    stack<int> s1;
    stack<PII> s2;

    int cnt = 0, top = 0;

    for(int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        s1.push(num);
    }

    s2.emplace(s1.top(), N);
    s1.pop();

    while(!s1.empty())
    {
        int cur = s1.top();
        s1.pop();

        int s = s1.size();
        while(!s2.empty() && cur > s2.top().first)
        {
            arr[s2.top().second] = s + 1;
            s2.pop();
        }
        s2.emplace(cur, s + 1);
    }

    for (int i = 1; i < N+1; i++)
        cout << arr[i] << ' ';

    return 0;
}