백준 2493번 탑 with cpp

백준 2493번 탑 문제

문제링크 Q_2493

Stack 을 이용하여 문제를 풀어보자.

우선 이 문제는 탑을 왼쪽부터 오른쪽 방향으로 차례로 세우는데, 레이저는 반대로 발사한다.
그리고 자신보다 높은 탑이 있다면 그 탑의 번호를 반환한다.

• 우선 탑의 번호와 높이를 Stack 에 보관한다. 그래서 pair 를 사용한다.

• 내가 입력하는 높이와 현재 Stack 의 top() 을 비교하여 바로바로 처리해보자.

#include <iostream>
#include <stack>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    stack<pair<int, int>> S;
    int N, t;
    cin >> N;
    S.push(make_pair(0, 100000000));
    for(int i = 1; i <= N; i++)
    {
        cin >> t;
        while(S.top().second < t) S.pop();
        cout << S.top().first << ' ';
        S.push(make_pair(i, t));
    }
    return 0;
}

코드 순서(입력 , pop(), 출력, push())에 유의하자!