[백준 2493번] 탑 (C++)

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

2493번: 탑

스택을 이용하는 문제로 이전에 포스팅했던 스카이라인 쉬운거와 오큰수하고 비슷한 문제이다.

자신만만하게 들어갔는데 한번pop한 탑은 다시 넣어줄필요가 없는데(어차피 뒤에 더 큰 탑이 있어서 거기에 걸림) 왠지 모르겠지만 다시 넣어버려서 시간초과좀 걸렸다.

아쉽다. 그리고 파이썬을 사용할때는 튜플이 익숙해서 편하게 사용했지만 C++에서는 아직 pair쓰는게 익숙하지 않아서 그냥 인덱스용 벡터 하나 더 만들었다가도 시간초과가 걸렸다.

결국 파이썬으로 풀까하다가 그냥 다시 C++넘어와서 pair사용해서 풀었다.

또 deque는 인덱싱이되서 deque로 풀려 했으나 deque의 인덱싱은 시간복잡도가 O(n)이라서 시간초과에 걸렸다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#define endl "\n"

using namespace std;
int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int n, top;
  cin >> n;
  stack<pair<int,int>> stack;
  vector<int> top_num;
  for(int i = 0; i < n; i++){
    cin >> top;
    while(!stack.empty()){
      if(stack.top().second > top){
        top_num.push_back(stack.top().first + 1);
        break;
      }else stack.pop();
    }
    if(stack.empty()){
      top_num.push_back(0);
    }
    stack.push(make_pair(i,top));
  }
  for(auto loop : top_num){
    cout << loop << ' ';
  }
}