백준 2493 탑 c++

[문제 링크]

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

[입출력 예]

입력	출력
5 6 9 5 7 4	0 0 2 2 4

[1차시도 - 시간초과 57%]

#include <bits/stdc++.h>
#define MAX_N 500001

using namespace std;

int a[MAX_N];
int ans[MAX_N];
int recent_max = -1;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;

    for(int i=0; i<n; i++){
        cin>>a[i];
        if (recent_max>0 && a[i]>recent_max){
            cout<<0<<" ";
            recent_max=a[i];
            continue;
        }
        int temp=i-1;
        while(true){
            if (temp==-1) break;
            if (a[temp]>recent_max){
                recent_max=a[temp];
            }
            if (a[temp]>=a[i]){
                break;
            }
             temp--;

        }

        cout<<temp+1<<" ";
    }

    return 0;
}

[소스코드]

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int N;
stack<pair<int,int>> tower;

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin>>N;
  // 첫 값으로 최대값을 넣음.
  tower.push({100000001,0});
  for (int i= 1; i<=N; i++){
    int height;
    cin>>height;
    // 현재 height보다 높은 top이 나올 때까지 제거
    while (tower.top().X <height)
      tower.pop();
      cout<< tower.top().Y<<" ";
      tower.push({height,i});
  }
}

// 스택 문제의 본질은..?
// top부터 하나씩 파서 과거의 데이터를 조회해야하는데,
// 스택에는 꼭 필요한 정보만 있어야함. 꼭 필요한 정보가 아니면
// 시간복잡도를 위해서 아예 스택에 보관하지 않는 게 낫다.
// 이 문제는 0번인덱스부터 내림차순으로 요소들이 쌓이게 된다.

[출처]

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x05/solutions/1874.cpp