[백준 2493] 탑

문제 바로가기

2493번: 탑

스택으로 푼다는 힌트를 받고 풀었다

그냥 봤을 땐 감 1도 안왔는데..

 

그림으로 여러 경우를 그려서 생각해보니 현재의 탑 길이보다 크면서 가장 가까운 거리에 있는 탑에 레이저가 닿는다는 사실을 알 수 있었다.

그래서 스택에 탑의 길이와 번호를 함께 넣어주는데, 그 전에 스택을 탐색하며 현재 탑의 길이보다 짧은 탑은 쓸모 없는 정보이기 때문에 pop해준다.

현재 탑보다 길이가 긴 탑을 만나면 그 때 그 탑의 번호를 출력하고, 현재 탑의 길이를 push하면 된다.

 

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

long top[500001];
int N;
stack<pair<long,int>> s;

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> top[i];
    }

    s.push({ 100000000, 0 });

    for (int i = 1; i <= N; i++)
    {
        pair<long,int> light_top = s.top();
        while (light_top.first < top[i])
        {
            s.pop();
            light_top = s.top();
        }

        cout << light_top.second << " ";

        s.push({ top[i], i });
    }
    return 0;
}