[백준] 2493 탑 C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int answer[N];
    stack<pair<int, int>> s;
    // 입력된 height가 스택 top보다 크면, stack이 empty가 될 때 까지 pop
    vector<int> height;


    for(int i=0;i<N;i++) {
        int n;
        cin >> n;
        height.push_back(n);
    }

    for(int i=0;i<N;i++) {
        if(s.empty()) answer[i] = 0; 
        // 1) 입력받은 수신탑의 크기가 기존 스택의 top 보다 클 때
        else if(height[i] > s.top().second && !s.empty()) {
            while(!s.empty()) { 
                if(s.top().second > height[i]) break;
                s.pop();
                }
            if(s.empty()) answer[i] = 0;
            else answer[i] = s.top().first;
        } 
        // 2) 입력받은 수신탑의 크기가 기존 스택의 top 보다 작을  때
        else if(height[i] < s.top().second && !s.empty()) {
            answer[i] = s.top().first;
        }
        s.push({i+1, height[i]});
    }

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

원리는 간단하고 금방 풀 수 있을 것 같았지만....^^

이 문제에서 스택은 수신을 받을 수 있는 수신탑인지를 판별하기 위해 사용한다
우선, 스택이 비어있을 때, 즉 수신할 수 있는 탑이 없을 때, answer 배열에 0을 대입한다.

• 입력받은 수신탑의 크기가 기존 스택의 top보다 크다면, pop을 해줘야 한다. ( = 스택의 top은 입력받은 수신탑의 신호를 받을 수 없음)
  1) 스택을 pop하는 중, 입력받은 수신탑의 크기보다 스택의 top이 크면 pop을 멈춘다.
• 입력받은 수신탑의 크기가 기존 스택의 top보다 작을 때, 즉 스택의 top이 입력받은 수신탑의 신호를 받을 수 있을 때
  스택의 탑의 인덱스를 가짐