[백준] 2493번: 탑

 

스택 구현 문제이다.

 

 

 

 

 

 

 

 

 

 

 

처음 생각했던 접근방식

 

처음에는 골드 문제치고 상당히 쉽고 직관적으로 이해할 수 있었다.

왼쪽으로 레이저를 보낼 때 수신하는 탑의 높이가 송신한 탑의 높이보다 크거나 같으면 신호를 수신할 수 있다.

 

그렇기 때문에 가장 단순하게 먼저 떠올린 방식은 맨 오른쪽 탑부터 역 순회하면서 가장 먼저 수신하는 탑의 인덱스를 반환하는 거였는데,

당연히 앞의 탑을 일일이 확인해야하므로 시간복잡도가 O(n^2)에 가까워지고, 이는 n이 50만 이하라고 했을 때 매우 비효율적이다.

 

따라서 cin으로 입력을 받는 동시에 결괏값을 결정지을 수 있으면 좋을 것이라 생각했고,

탑의 높이는 이전보다 크거나, 같거나 작은 경우밖에 없으므로 각각의 경우에 따라 알맞은 논리를 사용하면 될 것이다.

 

 

 

 

 

 

 

합당한 접근방식

 

 

 

앞에 있는 탑의 높이가 현재 신호를 보내는 탑의 높이보다 크다면, 신호는 앞에 멈출 것이기 때문에 앞의 탑의 인덱스를 반환한다.

앞에 있는 탑의 높이가 현재 신호를 보내는 탑의 높이보다 작다면, 앞에 있는 탑은 이후에 송신할 탑보다 항상 작으므로, 쓸모가 없다.

 

즉, 스택 자료구조를 활용해서, 현재 송신하는 탑의 높이가 앞에 있는 탑의 높이보다 큰 경우에 pop을 해주고,

이후에는 신호를 받으므로 인덱스를 반환하고 송신한 탑의 정보를 스택에 push한다. 

 

#include <iostream>
#include <stack>
#include <utility>
 
using namespace std;
 
int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N; 
    cin >> N;
    
    stack<pair<int,int>> lazerTop;
    lazerTop.push({100000001,0});
    for(int i=1; i<=N; i++){
        int h;
        cin >> h;
        
        //h가 기존 스택 높이 값보다 클 경우
        while(lazerTop.top().first < h && !lazerTop.empty()){
            lazerTop.pop();
        }
        cout << lazerTop.top().second << ' ';
        lazerTop.push({h,i});
    }
 
    return 0;
}

 

스택을 사용하면 효율적으로 풀리는 문제를 많이 풀어보지 않아서, 처음에 문제를 풀 때 감은 어느정도 있었지만,

명쾌하게 해답을 이끌어내지는 못했다. 스택 자료구조가 잘 쓰일 수 있는 대표적인 문제인 것 같다.

또다른 다양한 경우에 사용될 수 있기에 미리 연습을 해놔야겠다 :)