[ 백준 2493 ] 탑 (C++) - stack, priority_queue

---

🔗 문제 링크

2493번: 탑

---

💡 문제 풀이 및 해석

1. 탑은 왼쪽에서 오른쪽으로 만들고, 탐색은 오른쪽에서 왼쪽으로 진행된다.
2. 자신보다 크거나 같은 탑을 만나면 더 이상 신호가 왼쪽으로 가지 않는다.
3. 1번과 2번을 종합하면, 오른쪽 탑부터 왼쪽 탑으로 탐색을 해야 하는데, 현재 탑을 기준으로 오른쪽에 있는 탑들의 집합에서 가장 작은 탑보다 작다면, 현재 탑도 집합에 넣어주고, 아니라면 현재 탑의 높이보다 작거나 같은 탑들은 현재 탑에 수신된다고 표시해주면 된다.
4. 종합적으로 input은 stack으로 쌓아주고, 탑의 집합은 priority_queue 로 만들어주면 된다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

int N;
stack<int> s;
priority_queue<pair<int,int>> q; // height, num
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int Height; cin >> Height;
        s.push(Height);
    }
}

void sol() {

    int* answer = new int[N + 1];
    for (int i = 0; i <= N; i++) answer[i] = 0;

    while (!s.empty()) {
        int curHeight = s.top(); // 높이
        int curNum = s.size(); // 번호
        s.pop();

        while (!q.empty()) {
            int MIN = - q.top().first; // 오른쪽 빌딩의 최소 높이
            int num = q.top().second; // 최소 높이의 빌딩의 번호
            if (curHeight >= MIN) {  // 오른쪽의 가장 작은 빌딩보다 내가 크다면 수신가능
                answer[num] = curNum;
                q.pop();
            }
            else { // 더 이상 자신보다 작은 빌딩이 오른쪽에 없다면
                break;
            }
        }
        q.push({-curHeight,curNum});
    }

    for (int i = 1; i <= N; i++)
        cout << answer[i] << " ";

}

int main() {

    input();
    sol();

    return 0;
}

---

🤔 문제 후기

맞고 나서 알고리즘 분류를 봤는데, stack과 data_structure 만 써있는데, 솔직히 stack만 사용해서는 어떻게 풀까? 생각도 해봤는데, 생각이 잘 나지 않는다. pq를 쓰지 않았다면 어떻게 풀었을지는 아직 모르겠다.