백준 : 2493 - 탑

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

 

 

;;.. 풀긴 했는데 찝찝해서 찾아보니까 monotonic stack이란걸 이용하는 문제였다..

 

내 풀이와 monotic stack을 이용하는 두가지 방법을 같이 소개해보려고 한다.

 

방법1 : 그냥 빡구현 하기

이런 빌딩숲을 생각했을 때,,,,,,,,,,,,

answer 벡터에, 레이더가 닿는 빌딩의 인덱스를 저장한다고 생각해보자

(없는경우 0을 저장한다. 첫번째 빌딩은 0인게 확정됨)

4번 빌딩까지 답을 구했다고 생각하면 위와같이 빨간글씨 숫자가 answer 벡터에 저장되어 있을것이다.

여기서 5번 빌딩의 답을 구하려고 하면,,,,

바로 옆에 있는 4랑 비교해본다 => 4가 더 작으므로, 더 왼쪽으로 이동해야 하는데

여기서 4보다 작은애들은 고려할 필요가 없다! (어짜피 안됨)

그러니까 4번빌딩의 answer에 저장된 index로 바로 넘어가 버린다

즉... 5번빌딩을 정할때는 4번빌딩과 비교 후 2번빌딩과 비교한다!

    하나씩 비교할때보다 숫자를 훨씬 줄일 수 있게된다

=> 이런식으로 가다가,,, 자기보다 큰 빌딩을 만난순간, answer에 그 빌딩의 index를 저장해준다

(없으면 쭉쭉 가다가,,, answer가 0인 빌딩을 만났을 때, answer에 0을 저장해준다)

 

이렇게 해서 통과를 했다....

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

using namespace std;

bool comp(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}


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

    int n;
    cin >> n;
    vector<int> tops;
    for(int i = 0; i<n; i++){
        int temp;
        cin >> temp;
        tops.push_back(temp);
    }

    vector<int> answer;
    answer.push_back(-1);
    for(int i = 1; i<n; i++){
        if(tops[i] <= tops[i-1]){
            answer.push_back(i-1);
            continue;
        }else if(answer[i-1] == -1){
            answer.push_back(-1);
            continue;
        }
        int next_index = answer[i-1];
        while(true){
            if(tops[next_index] >= tops[i]){
                answer.push_back(next_index);
                break;
            }else if(answer[next_index] == -1){
                answer.push_back(-1);
                break;
            }else{
                next_index = answer[next_index];
            }
        }
    }

    for(int i = 0; i<n; i++){
        cout << answer[i] + 1<<" ";
    }

    return 0;
}

 

근데 아무리 생각해도 이상했다.. 분명 자료구조 문제집에서 찾은 문제인데 왜 그냥 구현이지???

정답은 monotonic stack이었다!

 

---

방법2 : monotonic stack

https://usowelcome.tistory.com/113

monotonic stack

 

위 글에서는 오른쪽에서 제일 큰거로 생각했다...

이 문제는?? 그냥 top배열의 숫자 (높이숫자)를 찐 숫자로 보고,,,, 왼쪽에서 제일 큰걸로 보면 된다!

ㅎㅎ... 이게 더 간단할지두...