[백준 2493] 탑

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

✍️ 첫번째 접근

N개의 탑들의 높이를 N번 입력받아서 stack에 저장하고 현재 stack의 top에 있는 값과 top 아래에 있는 값을 비교하여 만약 top에 있는 값이 크다면 맨처음 top에 있는 값이 더 작을 때까지 pop을 하고 그 pop한 값들을 저장하고 있는다. 만약, 맨처음 top에 있는 값이 현재 top에 있는 값보다 더 작다면 그 index를 저장하고 지금까지 pop했던 값들을 다시 stack에 넣어준다.
필자는 위와 같은 형태를 stack에 empty일 때까지 반복하였는데 그 결과, 시간초과를 초래하게 되었다. 아마 stack을 계속해서 줄이고 늘리는 과정에서 발생한 거 같다.

#include <bits/stdc++.h>
using namespace std;
int main(void){
    int input;
    scanf("%d",&input);
    stack<int> s;
    int res[input], index = 0;
    fill(res, res+input, 0);
    int N = input;
    while(input--) {
        int num;
        scanf("%d",&num);
        s.push(num);
    }

    vector<int> v;
    while(true) {
        int value = s.top();
        int cnt = s.size();
        s.pop();

        while(true) {
            --cnt;
            if(s.empty()) {
                for(int i = v.size()-1; i >= 0; i--) {
                    s.push(v[i]);
                }
                res[index++] = cnt;
                v.clear();
                break;
            }
            if(value > s.top()) {
                v.push_back(s.top());
                s.pop();
            }
            else {
                for(int i = v.size()-1; i >= 0; i--) {
                    s.push(v[i]);
                }
                res[index++] = cnt;
                v.clear();
                break;
            }
        }

        if(index == N) {
            break;
        }
    }

    for(int i = index - 1; i >= 0; i--) {
        printf("%d ",res[i]);
    }

    return 0;
}

✍️ 두번째 접근

미리 stack에 N개의 탑들의 높이를 입력받고 처리하는 것이 아니라 한번씩 입력받을 때마다 과정을 처리하려고 한다. stack에 이미 값이 존재하다면 현재 입력받은 값과 비교하여 stack에 존재한 값이 더 클 경우 index값을 바로 출력한다. 만약, stack이 empty라면 첫번째로 입력받은 경우인데 이보다 전에 입력받은 경우는 없으므로 0을 출력한다.

#include <bits/stdc++.h>
using namespace std;
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, value, index = 0;
    cin >> N;
    stack<int> s;
    int arr[N+1];
    fill(arr,arr+N+1,0);

    for(int i = 0; i < N; i++) {
        cin >> value;
        while(!s.empty()) {
            if(arr[index] >= value) {
                cout << s.top() << ' ';
                break;
            }
            else {
                s.pop();
                --index;
            }
        }
        if(s.empty()) {
            cout << "0 ";
        }
        ++index;
        s.push(i+1);
        arr[index] = value;
    }


    return 0;
}