[백준/C++] 2493번: 탑

문제

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

---

문제 요약

N개의 탑들이 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 주어진다.

 

모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평해하게 수평 직선의 왼쪽 방향으로 발사한다.

 

또한, 모든 탑은 레이저 수신기를 하나씩 갖고 있다.

+ 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

 

각 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 출력한다.

---

코드

#include <iostream>
#include <stack>

using namespace std;

int n;

stack<pair<int, int>> st;

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        int h;
        cin >> h;

        // 스택에서 i번째 탑보다 높은 탑을 만날 때까지 꺼내기
        while (!st.empty()) {
            if (st.top().second > h) {
                cout << st.top().first << " ";
                break;
            }
            
            st.pop();
        }
        
        // 왼쪽에 i번째 탑보다 높은 탑이 없는 경우
        if (st.empty()) cout << "0 ";

        // i번째 탑을 스택에 삽입
        st.push(make_pair(i, h));
    }

    return 0;
}

---

코드 설명

모노톤 스택을 이용한다.

 

기본적인 아이디어는 스택의 원소들을 오름차순 또는 내림차순 상태를 유지하는 것이다.

 

1. i번째 원소에 대해, 스택 맨 위에 있는 원소와 크기를 비교한다.

 

2. 스택 맨 위 원소가 i번째 원소보다 크거나 작거나 스택이 빌 때까지 원소를 꺼내고, 자신을 삽입한다.

 

=> i번째 원소보다 왼쪽에 있는 원소 중에서 처음으로 나오는 x 미만 / 초과 수의 위치와 값을 알 수 있다.

---

고찰

모노톤 스택에 대한 이해와 문제 풀이가 더 필요하다.