[BOJ] C++ 2493 탑 - 스택을 써야하는 경우

2493번: 탑

예제

5
6 9 5 7 4

ans : 0 0 2 2 4

---

문제를 풀 때 사용할 수 있는 조건들을 생각해 보자.

 

1. 첫 번째 탑은 무조건 수신할 탑이 없다.

2. 두 번째 이후의 탑은 자신보다 큰 탑 중 왼쪽 방향으로 가장 가까운 탑이 수신한다.

 

이 조건을 보고 스택을 떠올렸다.  스택을 메인 알고리즘으로 사용한 이유는 가장 최근에 들어온 데이터 중 조건에 맞는 데이터를 빼야 하는 조건부 후입선출 문제이기 때문이다. 처음에는 자신보다 높은 탑을 스택에서 고르기 위해 탑의 높이를 저장하는 원본 스택과 그대로 카피한 복제 스택으로 구성했다. 그리고 자기보다 높이가 큰 탑이 나올 때까지 복제 스택에서 pop 하면서 탐색하려 했다. 그대로 시간초과가 떠서 다시 생각해 보았다.

 

스택에 데이터를 넣으면서 바로 조건을 충족시키는 방법이 있었다. 스택에 새로운 데이터를 넣는데, 기존 스택에 있던 탑들이 새로운 탑보다 높이가 낮다면 싹 다 수신받을 수 없다. 그래서 새로 들어온 탑보다 낮은 탑들은 모두 pop 해줘도 된다. 근데 그럼 새로 들어온 탑보다 높이가 높은 탑은 pop 안 됐는데 어떡함?? 이런 상황에서는 다음에 새로 들어온 탑보다 높이가 높은 탑이 들어오면 pop 되므로 신경 안 써도 된다.

/** 스택 2493 탑 **/
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

    int N;
    cin >> N;
    vector<int> res;
    res.push_back(0);

    stack<pair<int, int>> s;
    // 초기값 설정, 맨 처음 들어온 높이는 어차피 수신 못하고 스택에 저장해야 한다.
    int x;
    cin >> x;
    s.push(make_pair(1, x));

    for (int i = 1; i < N; i++)
    {
        int height;
        cin >> height;
        // 이제 스택을 탐색하면서 현재 높이보다 작은건 다 pop하고 큰거 나오면 그거 답으로 하면 된다.
        // 작은건 다 pop해도 되는 이유는 어차피 현재 높이보다 작으면 이후의 입력에서 안쓰기 때문이다.
        while (!s.empty())
        {
            if (s.top().second > height)
            {
                res.push_back(s.top().first);
                break;
            }
            else
            {
                s.pop();
            }
        }
        if (s.empty())
            res.push_back(0);
        s.push(make_pair(i + 1, height));
    }

    for (auto x : res)
        cout << x << " ";
}