[BOJ/C++] 탑(2493번)

1. 개요

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

2493번: 탑

1-1. 설명

통신 연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위해 실험하고 있다. 실험을 위해 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선 왼쪽부터 오른쪽 방향으로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단하나의 탑에만 수신이 가능하다. 탑들의 개수 N과 탑들의 높이가 주어질때, 각각 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지 알아내는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 탑의 수를 나타내는 정수 N이 주어지며, N은 1 이상 500,000 이하

 - 둘째 줄에는 N개의 탑들이 높이가 직선 상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어지며, 탑 높이는 1 이상 100,000,000 이하 정수

---

2. 구현

2-1. 풀이

문제를 보고 스택으로 푸는 문제임은 깨달았으나, 스택에서 추가적으로 변수에 저장해 계산하는 부분에서 시간초과가 났다. 단순히 스택만으로 계산할 수 있는 방법을 고안하던 중 다른 사람의 풀이를 참고하여 풀었다. 

반복문을 통해 탑의 높이를 입력 받을 때, 스택이 비어있으면 비교할 대상이 없으므로 0을 출력한다. 스택이 비어있지 않으면, 스택의 top과 현재 탑의 높이를 비교한다. 현재 탑 높이가 top보다 높으면 스택에 저장된 top은 필요 없어지므로, pop을 진행한다. 만약 현재 탑 높이가 top보다 낮으면 top의 인덱스를 출력한다. 후에 이 값을 스택에 저장한다. 

스택만으로 잘 생각하면 금방 구현하는 알고리즘이었다. 

2-2. 코드 

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 500000;

struct Node {
    int tower, num;
};
stack<pair<int, int>> towers;
Node result[MAX_NUM];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, num;
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> num;
        
        while (!towers.empty()) { // 스택이 비어있지 않을 때
            if (num > towers.top().first) { // top보다 num이 더 클 때
                towers.pop(); // top은 쓰일 일이 없으므로 pop
            }
            else if (num < towers.top().first) { // top보다 num이 더 작을 때
                cout << towers.top().second << ' ';
                break;
            }
        }
        if (towers.empty()) cout << "0 "; // 스택이 비어있으면 0 출력
        towers.push({num, i+1});
    }
    return 0;
}