[C/C++] 백준 #2493 탑(스택)

이번 문제는 스택을 이용해서 간단하게 풀 수 있는 문제입니다.  현재 골드 레벨로 설정되어 있지만, 그보다 낮은 레벨이어도 될 것으로 봅니다.

 

communication towers

 

문제의 링크입니다.

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

2493번: 탑

 

n개의 타워가 왼쪽부터 차례대로 일렬로 서 있습니다.  각각의 탑 꼭대기에는 신호를 송신하는 장치가 있고, 왼쪽으로만 수평 방향으로만 송신할 수 있습니다.  모든 탑에서는 어떤 높이에서든 송신된 신호를 받을 수 있습니다.  송신된 신호는 첫번째 만나는 탑에 수신이 됩니다.

 

모든 탑에서 동시에 신호를 송신했을 때, 해당 신호를 수신하는 탑을 찾으라는 것입니다.

 

예를 들어서 높이가 3 7 2 6 인 탑들이 있다면, 6에서 송신한 신호는 2의 높이 탑에서는 받을 수가 없습니다.  적어도 6이상의 높이가 되어야 합니다.  그래서 높이가 7인 탑이 수신을 합니다.  2에서 송신한 신호도 높이가 7인 탑이 수신합니다.  높이 3인 탑은 왼쪽에 송신탑이 없기 때문에 수신받을 수 있는 탑이 없습니다.  높이가 7인 탑은 왼쪽에 7 이상의 탑이 없기 때문에 수신할 수 있는 탑이 없습니다.

 

이것을 스택으로 만들어 풀게 되면,

3이 들어오면 스택이 비어 있으므로 수신할 탑이 없습니다.  (사실상 첫번째 결과는 항상 0입니다.)

3을  스택에 push 합니다.

7이 들어오면, 스택에 3이 있습니다.  7보다 작은 값은 스택에서 제거를 합니다.  그러면 스택이 비어있게 되고, 결과값을 0을 적고 7을 스택에 push 합니다.

2가 들어오면, 스택에 가장 위에 있는 것이 7이므로 7의 탑 인덱스 2를 출력합니다.  그리고 2를 스택에 push합니다.

6이 들어오면, 6보다 작은 값들을 스택에서 제거를 하고 7을만나게 되면 7의 탑 인덱스 2를 출력합니다.  그리고 6을 스택에 push합니다.

 

전체적인 시간복잡도는 push 비용과 pop 비용이 모두 n에 비례하므로 \(O(n)\)이 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2493 - Tower
//        - by Aubrey Choi
//        - created at 2019-06-27
//------------------------------------------------
#include <stdio.h>

struct Element { int index, value; } stack[500000];
int main()
{
    int n, sp = 0, t;
    scanf("%d", &n);
    stack[0].value = 1000000000;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &t);
        while(stack[sp].value < t) sp--;
        printf("%d ", stack[sp].index);
        stack[++sp].index = i;
        stack[sp].value = t;
    }
}