[Seop's의 코드풀이] 백준 2493, 탑 - Python

이번에 풀어볼 문제는 백준 2493번 '탑'이라는 문제입니다.

문제는 다음과 같습니다.

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

2493번: 탑

 

단순하게 생각해서 문제를 풀어보면 다음과 같은 풀이법이 있을 수 있습니다.

1. 주어진 배열을 뒤에서 부터 읽습니다.

2. 읽은 배열부터 다시 뒤에서 부터 읽어 자신보다 큰 수가 나오면 정답 배열에 해당 인덱스를 저장합니다.

 

참 간단하죠? 하지만 이러한 방법은 굉장히 많은 시간이 소요되게 됩니다. 그래서 시간초과가 발생하게 됩니다.

 

필자는 스택을 활용해서 위 문제를 풀었습니다.

스택에 저장하는 아이디어는 다음과 같은 방식을 사용했습니다.

1. 먼저 0번째 값과 인덱스를 스텍에 적재합니다. (2차원 배열이 됩니다.)

2. 1번 인덱스부터 차례대로 읽기 시작합니다.

3. 만약 스텍의 최상위 값이 현재 읽고 있는 값보다 작을 경우 POP을 진행하고 현재 값과 인덱스를 PUSH합니다.

4. 3번 이외의 경우에는 현재 값과 인덱스를 PUSH 합니다.

 

이런 방식으로 진행할경우 현재 값보다 큰 인덱스를 찾을때 POP을 해주면서 비교를 해주고

현재 값보다 큰 값이 나오면 해당 인덱스를 정답 배열에 저장해 주면 됩니다.

 

스텍을 활용해서 푼다면 속도가 느린 Python으로도 충분히 풀 수 있는 문제였습니다.

전체적인 코드는 다음과 같습니다. 질문과 피드백은 언제나 감사드립니다.

 

import sys
input = sys.stdin.readline

def checkStack(tall) :
    while stack :
        if stack[-1][0] < tall :
            stack.pop()
        else :
            answer[i] = str(stack[-1][1] + 1)
            break
    stack.append([tall, i])


if __name__ == "__main__":
    N = int(input())
    top = list(map(int, input().split(" ")))
    answer = ['0' for i in range(N) ]
    stack = [ [top[0], 0] ]
    for i in range(1, N) :
        checkStack(top[i])
    print(" ".join(answer))