(C++) 백준 2493번 - 탑

문제 링크 : https://www.acmicpc.net/problem/2493

2493번: 탑

풀이

처음에 다음과 같이 풀어보았다.

#include <iostream>
#include <stack>

using namespace std;

stack<int> T, tmp, answer;

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

    int n;
    cin >> n;
    while(n--){
        int i;
        cin >> i;
        T.push(i);
    }
    while(1){
        int num = T.size()-1; // 왼쪽 탑부터 시작
        if(num == 0){ // 탑이 하나 남았다면 0을 push하고 break
            answer.push(0);
            break;
        }
        int top = T.top(); 
        T.pop(); // 송신 시작
        while(1){ // 현재 탑의 높이(top)보다 높은 탑이 나올 때까지 반복
            if(T.empty()){ // 더 높은 탑이 없다면 0을 push
                answer.push(0);
                while (!tmp.empty()) { // 뺐던거 다시 집어넣기
                    T.push(tmp.top());
                    tmp.pop();
                }
                break;
            }
            if(top < T.top()) { // 더 높은 탑이 나왔다면 몇번째 탑인지 그 값을 push
                answer.push(num);
                while (!tmp.empty()) { // 뺐던거 다시 집어넣기
                    T.push(tmp.top());
                    tmp.pop();
                }
                break;
            }
            // 그렇지 않다면 나올 때까지 빼면서 반복
            num--;
            tmp.push(T.top());
            T.pop();
        }        
    }
    while (!answer.empty()) {
		cout << answer.top() << " ";
		answer.pop();
	}
}

tmp라는 임시 스택을 만들어 높이가 낮아 pop시켰던 탑들을 저장했다가 다시 넣어주는 식으로 풀이를 진행했는데, 이렇게 하면 1억 개에 육박하는 테스트 케이스에 대해 실행하면 시간 초과가 발생한다.

 

시간 초과를 해결할 방법을 알 수 없어서 인터넷을 통해 풀이를 찾아보니 pair를 사용하고, 제일 처음에(0번째) 가장 높이가 높은 탑을 넣어놓는 방법을 알게 되었다. 그래서 이를 이용하여 풀이를 진행해보았다.

그 외에도 또 중요한 포인트는 오른쪽에 더 높은 탑이 들어오게 되면 그보다 왼쪽에 있는 탑들은 어차피 수신하지 못하므로 스택에서 제거해도 된다는 것이었다. 이 점이 시간초과를 발생하지 않게 하였다.

#include <iostream>
#include <stack>

using namespace std;

stack<pair<int,int>> T;

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

    int n;
    cin >> n;
    T.push({100000001, 0}); // 누구보다 큰 탑
    for(int i = 1; i <= n; i++){ // n번 반복
        int h; // 탑의 높이
        cin >> h;
        while(1){
            if(h < T.top().first){ // 더 큰 탑을 만나면
                cout << T.top().second << " "; // 그 탑의 높이 출력 후
                break; // while문 탈출
            }
            // 더 큰 탑을 만날 때까지 pop, 더 큰 탑이 오른쪽에 있기 때문에 굳이 스택에 남아 있을 필요가 없음
            T.pop();
        }
        T.push({h, i});
	}
}