(백준) 2493 – Top (C++)

by

쉬운 목차

문제

#2493: 탑(acmicpc.net)

2493호: 위

'추천 관련글,

첫 번째 줄에는 타워의 수를 나타내는 정수 N이 제공됩니다.

N은 1 이상 500,000 이하이다.

두 번째 줄은 사이에 공백을 두고 직선에 배치된 순서대로 N 타워의 높이를 제공합니다.

탑의 높이는 1입니다.

www.acmicpc.net

설명

스택을 활용하는 것입니다.

tower는 타워의 높이와 위치(인덱스)를 쌍으로 저장합니다.

선택한 인덱스의 타워 높이가 다음 인덱스의 타워 높이보다 낮으면 신호가 정상적으로 수신되어 해당 타워 높이를 출력합니다.

시간 초과를 방지하려면 빠른 I/O를 사용하십시오.

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N;
    cin >> N;
    
    stack<pair<int, int>> tower;
    for (int i = 1; i <= N; i++) {
        int height;
        cin >> height;
        
        while (!
tower.empty()) {
            if (tower.top().second > height) {
                cout << tower.top().first << " ";
                break;
            }
            tower.pop();
        }
        
        if (tower.empty()) {
            cout << "0 ";
        }
        
        tower.push({i, height});
    }
    
    return 0;
}