백준 2493 탑

백준 2493 탑 문제는 스택을 이용하여 해결하는 문제이다

도저히 스택을 활용할 수 없어서 그냥 구현이라도 해보자했는데 역시나 시간초과..

시간초과코드

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

vector<int> v;
vector<int> ans;
int N;
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    for(int i = N-1; i > 0; i--) {
        int tmp = v[i];
        for(int j = i-1; j >= 0; j--) {
            if(tmp < v[j]) {
                ans.insert(ans.begin(), j+1);
                break;
            }
            if(!j) ans.insert(ans.begin(), j);
        }
    }
    ans.insert(ans.begin(), 0);
    for(int a : ans) cout << a << ' ';
}

질문게시판에 스택을 활용하여 O(n^2)이 아닌 O(N)으로 해결할 수 있는 방법이 있다해서 열심히 고민했지만 결국 구글링

찾아보니 스택에 pair라는 것이 존재했다.
이는 스택은 스택인데 말 그대로 쌍을 이루는 값이 있는 것

풀이코드를 보면서 한 번에 이해되지 않음을 잠깐 자책하고
이제라도 알면 됐지라는 마음과 감탄의 마음으로 코드를 곱씹고 또 곱씹었다.

이번 기회를 통해 stack에서 pair의 존재를 알게 되었다.

중요 key point

1. 굳이 모든 탑의 높이를 입력받은 뒤 비교할 필요가 없다.
2. 옆에 숫자와 비교하면 된다.
3. 첫번째 탑의 빔을 맞는 탑은 없으니 무조건 0이다.

풀이코드

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

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

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    
    // 처음은 무조건 0이니 탑의 최대 높이보다 1이 큰 숫자를 넣어준다. 그리고 두번째 숫자는 출력할 인덱스값이다.
    tower.push({100000001, 0});
    
    for(int i = 1; i <= N; i++) {
    	int height;
        cin >> height;
        while(tower.top().first < height) tower.pop();
        cout << tower.top().second << " ";
        tower.push({height, i});
    }
}