[백준/C++] 2493번 탑

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

2493번: 탑

문제분석

맨 오른쪽부터 왼쪽으로 일정 높이를 가진 탑에서 신호를 송신하면 신호를 보낸 탑보다 높이가 높은 탑만 신호를 수신할 수 있다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서있다고 하자. 그러면, 높이가 4인 다섯번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 5인 탑을 지나쳐 높이가 9인 탑이 수신을 한다.

높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신하지 못한다.

입력으로는 첫째 줄에는 탑의 개수 N이 주어지고, 두번째 줄에는 각각 탑들의 높이가 주어진다.

출력으로는 각각의 탑에서 바라한 레이저 신호를 어느 탑에서 수신하는지를 출력한다.

코드

#include <iostream>
#include <stack>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    stack<pair<int,int>> s; // 인덱스와 탑의 높이를 같이 저장할 pair쌍
    int n, num;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> num;
 
        while (!s.empty()) { // 스택이 비어있지 않으면
            if (num < s.top().second) { // 스택 최상단에 저장된 탑의 높이와 비교
                cout << s.top().first << " "; // 수신가능하면 스택 최상단에 있는
                                              // 탑의 인덱스를 출력
                break;
            }
            s.pop(); // 높이가 낮으면 어차피 쓸모없으므로 Pop
        }
        
        if (s.empty()) { // 만약 스택이 비어있다면 = 수신할 수 있는 것이 없다 = 0 출력
            cout << 0 << " ";
        }
        s.push({ i + 1, num }); // 현재 탑을 스택에 push
    }
 
    return 0;
}

 

문제풀이

우선 값을 입력받고, 스택을 체크한다. 스택을 체크하였는데 비어있다면 내 왼쪽에는 탑이 없는 것이므로 0을 출력해준다.

만약 스택에 값이 들어있다면, 현재 입력으로 들어온 것과 스택의 top()과 비교를 한다.

만약 현재 입력값 > 스택의 top()이라면, 수신할 수 없는 탑이므로 pop하여 다음 스택값과 비교한다.

이를 스택이 빌 때 까지 반복한다.

반복하는 도중에

만약 현재 입력값 < 스택의 top()이라면, 정상적인 탑을 찾은 것이므로 스택의 top()에 해당하는 탑의 인덱스를 출력한다.

그리고 현재 입력으로 들어온 값과 인덱스를 pair쌍으로 스택에 저장한다.

​

※ 이 문제를 쉽게 해결하기 위해선 pair를 떠올리는 것이 중요했던 것 같다.