백준 2493번 탑: C언어, 파이썬 풀이

백준 2493 탑 문제 해설입니다.
내림차순으로 구성되는 규칙을 가진 스택과 더미 데이터를 활용한 구현을 설명합니다.
C언어와 파이썬, 두 언어로 최종 코드를 작성하였습니다.

전략

저번 오큰수 문제와 유사하다.
이번엔 좌큰수를 찾는 문제라고 봐도 무방하다.

또 탑의 높이가 아닌, 탑의 번호(위치)를 출력해야하는 점이 다르다.

내림차순 스택

스택에 탑의 높이를 저장한다. 스택은 항상 내림차순으로 정렬되어 있다고 가정한다.

내림차순이 깨지는 순간을 살펴보자 7, 5, 3, 2 다음 4가 나왔다.
이제 3, 2의 높이를 가지는 탑은 신호를 받을 수 없다. 4가 막고있기 때문이다.

3, 2를 스택에서 없애준다. 스택에는 7, 5 가 남아있다.
4의 신호를 받는 탑은 5이다. 이제 4를 스택에 넣어준다.

물론 출력 값은 탑의 높이가 아닌 탑의 번호다.
탑의 번호를 스택에 저장하고, 높이는 따로 지정한 배열에서 진행해줄 수 있다.

1-인덱싱 with dummy node

탑의 순서는 1부터 시작한다. 배열은 0부터 시작하니 약간 귀찮은 상황이라고 생각할 수 있다.
단, "레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다" 라는 조건을 잘 이용하면 위기를 기회로 바꿀 수 있다.

무슨 말이냐면.

타워 높이를 저장하는 배열에 0번째 index에 엄청 높은 가상의 타워가 존재해서, 모든 신호를 수신한다고 생각해보자.

이런 dummy 타워를 처음에 넣고 시작하면 특수한 예외처리 없이 일반화된 코드 작성이 가능하다.

입출력

저번 오큰수 문제에서, 반복문 내부에 scanf/printf와 같은 IO 함수와 다른 연산용 함수가 공존할경우 속도가 느려질 수 있음을 배웠다.

이번 문제에서도 반복문 안에서 스택의 top 원소를 반복적으로 출력하는 상황이 발생한다.
매 루프마다 printf를 호출하기보다 큰 버퍼에다가 값들을 저장했다가 한 번에 출력하면 어떨까 해서 시도해보았다.
확실히 속도가 빨라지긴 했다.

최종 코드

C언어 최종 코드

#include <stdio.h>

#define MAX_NUM_TOWERS 500000
#define MAX_TOWER_HEIGHT 100000000

// Tower heights, 1-indexed
int towers[MAX_NUM_TOWERS + 1];

// Stack of tower index, 1-indexed
// 0 is a dummy
int stack[MAX_NUM_TOWERS + 1];
int top = 0;

// 10 digits + 1 space
char output_buf[MAX_NUM_TOWERS * 11];
int buffer_size = 0;

int main(void)
{
    int num_towers;
    scanf("%d", &num_towers);

    for (int i = 1; i <= num_towers; i++)
    {
        scanf("%d", &towers[i]);
    }

    // Dummy tower for 1-indexing, tall enought to receive unreceived signals 
    towers[0] = MAX_TOWER_HEIGHT + 1;
    // maps to the dummy tower
    stack[top] = 0;

    for (int i = 1; i <= num_towers; i++)
    {
        // Pop shorter towers
        while (towers[i] > towers[stack[top]])
        {
            top--;
        }

        // Receiver index into output buffer
        buffer_size += sprintf(&output_buf[buffer_size], "%d ", stack[top]);

        // Push index
        stack[++top] = i;
    }

    printf("%s\n", output_buf);
}  

Python 최종 코드

어쩌다 풀게되어서 적어놓았다. 원리는 같다.

import sys

MAX_TOWER_HEIGHT = 100000000

n_towers = int(sys.stdin.buffer.readline())

# Dummy
idx_stack = [0]
tower_height = [MAX_TOWER_HEIGHT]
tower_height.extend(map(int, sys.stdin.buffer.readline().split()))

output = [0] * (n_towers + 1)

for tower_idx in range(1, n_towers + 1):
    while tower_height[idx_stack[-1]] < tower_height[tower_idx]:
        idx_stack.pop()
    output[tower_idx] = idx_stack[-1]
    idx_stack.append(tower_idx)

print(' '.join(map(str, output[1:])))