스택을 사용하는 대표적인 유형인 것 같다(스택 문제집에 방향만 다르고 똑같이 생긴 문제가 수두룩 빽빽함). 개인적으로 스택을 사용해야 하는 걸 모르면 접근이 쉽지 않을 것 같다.

문제 분석

높이가 서로 다른 탑이 일렬로 늘어서있고, 한쪽 방향으로 자신보다 높은 가장 가까운 탑의 위치를 찾는 문제이다. 다른 문제들도 방향이나 찾는 조건에만 차이가 약간씩 있고 비슷한 구조를 띈다.

Key idea

이 문제는 앞에서부터 자신보다 높은 가장 가까운 탑을 찾아야하므로, 앞에서부터 아래 두 과정을 반복하면 된다.

1. 스택의 top이 현재 높이보다 클 때까지 pop
2. 스택의 top이 현재 높이보다 크면 push

이렇게 하면 스택의 top에는 나보다 높고 가장 가까운 내 앞쪽 탑의 높이가 유지된다.

Solution

위의 아이디어를 코드로 구현한 것이다. 앞쪽에 자신보다 높은 탑이 없으면 0을 반환해야 하므로 스택의 첫번째 원소에 최대높이+1을 push하여 초기화했다.

n = int(sys.stdin.readline())
height = list(map(int, sys.stdin.readline().strip().split(" ")))
height.insert(0, 100000001)

stack = [(0, height[0])]
result = []
for i in range(1, n+1):
    while stack[-1][1] < height[i]:
        stack.pop()

    result.append(stack[-1][0])
    stack.append((i, height[i]))

for i in result:
    print(i, end=" ")

• BOJ 2493 탑