[백준 2493] 탑 - C++

문제접근

이 문제는 n이 5*10^5 이므로, 완전탐색으로 풀면 10^10승이 돼서 시간 초과가 난다. 따라서 O(n) 풀이를 생각해야 한다.

문제 분류가 stack이어서, stack을 이용하려고 노력했다.

관찰을 하다 보면,

현재 넣을 값(cur)이 지금까지 받은 값(top)보다 클때, 지금까지 받은 값은 의미가 없어진다.

임을 알 수 있다.(그 후 어떤 값을 받더라도, 현재 탑이 송신 할 것이기 때문에)

따라서,

1. cur이 top보다 크면, stack에서 cur보다 큰 값이 나올때 까지 pop을 한다.

2. cur이 top보다 작으면, stack에 cur을 넣는다.

위와 같은 과정으로 문제를 풀면 된다.

cur < top 일때만 stack에 push를 하기 때문에 top값보다 cur이 크다면, stack에 있는 모든 값보다 cur이 크다.

 

교훈

stack STL에서 top함수를 이용할 때 empty를 유의해라.

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

#define X first
#define Y second

int ans[500];
void solve() {
  int n;
  cin >> n;
  stack<pair<int, int>> in;
  int cur;
  int ans;
  for(int i = 1; i <= n; i ++) {
    cin >> cur;
    ans = 0;

    while(!in.empty()) {
      if(in.top().X > cur) {
        ans = in.top().Y;
        break;
        } // 수신탑 찾음
      in.pop();
    }
    //ans[i] = in.top().Y; // 스택 맨 위에게 수신탑
    //cout << in.empty() << '\n';
    in.push({cur, i});
    cout << ans << ' ' ;
  }
}

// ************************************

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
}