백준 :: 2493번 탑 (Python)

문제 링크

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

2493번: 탑

접근 방식

문제를 보고 현재 탑보다 이전(왼쪽)에 있는 탑들 중 일단 거리가 가깝고, 현재 탑보다 높이가 크거나 같은 탑이 몇번 인덱스인지 확인하면 되겠다는 생각이 들었다.

예를 들어 예시 입력인 6 9 5 7 4 에서 높이가 5인 탑은 높이가 6인 탑이 있든 없든 상관이 없다.

그래서 스택으로 탑들을 쌓아나가면서 높이를 비교해나가기로 생각했다.

1. 스택이 비면 0 출력
2. 수신할 수 있는 탑을 찾을 때까지 스택 탐색
   • 현재 탑보다 작은 탑은 pop (뒤 탑들 입장에선 현재 탑보다 작은 앞쪽 탑은 필요없다)
   • 수신할 수 있는 탑을 찾으면 해당 탑의 인덱스 출력
3. 현재 탑을 스택에 push

풀이 코드

import sys

def input():
    return sys.stdin.readline()

N = int(input())
towers = list(map(int, input().split()))

stack = []
answer = []

'''
스택이 비면 0
수신탑 찾을 때까지 peek.
    나보다 작은 값은 뒤 탑들에겐 필요없으므로 pop
    수신탑 찾으면 해당탑의 idx + 1 출력
나 push
'''
for idx, tower in enumerate(towers):
    while stack:
        if stack[-1][0] < tower:
            stack.pop()
        else:
            answer.append(str(stack[-1][1]))
            break
    else:
        answer.append(str(0))
    stack.append((tower, idx+1))

print(' '.join(answer))

끝.