[백준] 2493번: 탑

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

2493번: 탑

앞서 푼 문제는 쉽게 문제를 접근해서 풀었다면, 이번에는 단순히 쉽게 접근하면 시간 초과로 풀 수 없다.

탑을 하나씩 접근하면서($O(N)$), 각 탑의 앞 탑들을 탐색하면 전체적으로 $O(N^2)$ 의 시간 복잡도가 나온다.

여기서 누적합으로 풀어야 하나 고민했지만 탑의 길이가 지나치게 길다는 점부터 고려의 대상에서 제외하였다.

 

효율적인 풀이를 고민하던 끝에 왜 탑을 순서대로 탐색하는 게 비효율적인지를 다시 고민해보았다.

불필요하게 이미 가려진 탑들까지 고려의 대상으로 포함한다는 게 문제였다.

그래서 가려진 탑은 제거하기 위해 Stack라는 자료구조를 활용했다.

앞에서부터 탑을 넣되, 현재 삽입하는 타워의 높이보다 크거나 동일한 경우는 Stack에 남기고, 작은 경우는 Stack에 제거한다.

 

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

stack<pair<long long,int>> towers;

int main() {
    int n;
    long long tower;
    cin >> n;
    vector<int> answer(n + 1);
    for(int i = 1;i <= n;i++) {
        cin >> tower;
        while(!towers.empty()) {
            long long front_tower = towers.top().first;
            int idx = towers.top().second;
            towers.pop();
            if(front_tower > tower) {
                answer[i] = idx;
                towers.push({front_tower, idx});
                towers.push({tower, i});
                break;
            }
            else if(front_tower == tower) {
                answer[i] = idx;
                towers.push({tower, i});
                break;
            }
        }
        towers.push({tower, i});
    }
    
    for(int i = 1;i <= n;i++) {
        cout << answer[i] << " ";
    }
}