BOJ 2493번: 탑

문제 링크: https://www.acmicpc.net/problem/2493

주어진 조건을 요약해보면, 어떤 탑은 그 왼쪽에 자신보다 큰 탑이 있어야 발사한 레이저 신호를 송신하는 탑이 존재한다는 것입니다.

스택과 pair를 활용하여, 탑의 위치와 높이를 저장하는 식으로 해결했습니다.

우선 입력이 들어왔을 때 스택이 비어있다면, 그 탑의 레이저를 송신할 대상이 없으므로 0을 출력하고 탑의 위치와 높이를 스택에 저장합니다.

스택이 비어있지 않을 때 입력이 들어오면, 입력된 탑의 높이와 스택에 저장된 탑의 높이를 비교합니다.

입력된 탑의 높이가 더 높으면, 기존의 탑을 스택에서 제거하고, 새 탑을 스택에 저장해둡니다.

입력된 탑의 높이가 스택에 비해 같거나 낮으면, 입력된 탑이 송신한 레이저는 스택의 탑이 수신하게 됩니다.

스택에 저장된 탑의 정보를 출력하고 다음 탑의 정보를 입력받도록 하면 됩니다.

문제에 주어진 예제 6, 9, 5, 7, 4로 설명해보면,

처음 탑은 pair<1, 6>으로 표현이 가능합니다. 왼쪽에 그 어떤 탑도 없으므로 레이저를 수신하는 탑이 없습니다. 0을 출력하고 <1, 6>을 스택에 넣습니다.

9를 입력받고, 스택에 저장된 탑의 높이 6과 비교합니다. 9가 더 크므로 두 번째 탑의 레이저도 수신할 수 있는 탑이 없습니다.

0을 출력하고 <1, 6>을 스택에서 꺼낸 다음 <2, 9>를 넣어둡니다.

5가 입력되면 9와 5를 비교하여 5가 더 작으므로, <3, 5> 탑의 레이저를 <2, 9> 탑이 수신하게 됩니다.

수신하는 탑의 번호 2를 출력하고 다음 입력을 받습니다.

같은 방법으로 <4, 7> 탑의 정보도 <2, 9> 탑이 수신하게 됩니다.

4를 입력받았을 때, 7이 4보다 크므로 스택에 <4, 7>을 저장합니다.

입력이 끝날 때, 마지막 탑의 레이저를 수신하는 탑의 번호(=스택에 저장된 탑)를 출력하고 종료합니다.

C++

#include <cstdio>
#include <stack>
#include <utility>
using namespace std;

int main() {
    int num, input;
    stack<pair<int, int> > st;

    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &input);

        while(!st.empty()) {
            if(st.top().second > input) {
                printf("%d ", st.top().first);
                break;
            }
            
            st.pop();
        }

        if(st.empty()) printf("0 ");
        st.push(make_pair(i + 1, input));
    }

    return 0;
}

원래 cin, cout을 사용하여 작성하였는데 채점할 때 시간 초과가 나와서 printf, scanf를 사용하는 방식으로 실행 시간을 줄여서 해결했습니다.