백준 2493번: 탑 (C++)

문제

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

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

• 입력
  • 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
• 출력
  • 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

코드

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

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int num;
    cin >> num;

    stack<pair<int, int> > s;

    s.push(make_pair(0, 100000001));

    for (int i = 1; i <= num; i++){
        int height;

        cin >> height;

        while(s.top().second < height){
            s.pop();
        }
        cout << s.top().first << " ";

        s.push(make_pair(i, height));        
    }

    cout << "\n";
}

접근 및 풀이

결론부터 말하자면 스택을 이용해서 푸는 문제이다.

이 문제를 접하고 가장 먼저 드는 생각이 배열에 때려넣고 반복문을 돌리며 카운트 하는 건데, 그렇게 되면 시간 초과도 나고 효율적이지도 못할 것 같아 다른 방법을 생각해야만 했다. 아무리 생각해도 혼자의 힘으로는 풀 수가 없을 것 같아서 다른 사람들의 풀이를 좀 참고했다.

우선 접근해서 생각하는 방식을 바꿔보자. 탑이 모두 세워진 상태라고 생각하지 말고 탑을 하나씩 세우고 있는 과정이라고 생각하는 것이다. 탑을 하나씩 세우면서 이미 세워진 앞의 탑 중에 이 탑의 신호를 수신하는 가장 오른쪽의 탑이 어떤 것인지 기록하면 되는 것이다.

여기에서 조건을 세워보자.

첫 번째, 가장 먼저 들어간 탑은 신호를 수신할 수 있는 탑이 없다.
두 번째, 세워지는 탑보다 키가 작은 탑은 신호를 못 받기 때문에 답을 찾는 것에 영향을 주지 않는다.

그럼 이제 간단하게 스택을 이용해서 풀 수 있다. 스택은 해당 탑의 인덱스와 높이를 기록하는데, 탑을 세울 때 스택을 확인한 다음 스택의 top에 있는 탑의 높이가 현재 세워질 탑보다 큰 경우에는 현재 스택의 top에 있는 탑의 index를 출력한 후 스택에 push 된다. 현재 스택에는 내 신호를 수신할 수 있는 (현재 탑보다 키가 큰) 탑들이 세워진 순서대로 들어가 있기 때문에 스택의 top에 해당하는 탑의 index가 답이 된다. 만약 탑의 높이가 현재 세워질 탑보다 작은 경우에는 더 큰 값이 나올 때까지 pop하면 된다. (두번째 조건) 여기에서 탑의 높이의 최댓값보다 큰 0번째 탑이 존재한다고 가정하면 수신할 수 있는 탑이 존재하지 않는 탑들을 모두 0으로 기록할 수 있게 된다.(첫번째 조건)

한 요소 기준으로 앞에 들어온 값들과 비교하는 문제는 주로 스택을 이용하는 대표적인 문제인 것 같다. 자료구조를 이용하는 문제부터는 문제의 유형을 주로 파악해야 할 것 같다. 스택을 어떻게 이용하지? 를 깊게 생각해보면 다른 비슷한 유형의 문제나 다른 문제들을 풀 때 어떻게 풀어야 할지 도움이 될 것이다. 나도 처음에는 이걸 보고 어떻게 스택을 생각해? 라고 생각했지만 어쨌든 이 문제를 풀면서 스택을 어떤 방식으로 이용했는지 생각해 보면서 어떤 자료 구조를 어떤 상황에서 어떤 용도로 쓰는지를 조금이나마 익혔기 때문이다. PS는 역시 많은 문제를 풀어 봐야 한다는 것이 괜히 있는 말이 아니다.