[BOJ 2493] 탑(Python)

---

문제

탑

---

문제 해설

스택을 사용하여 가장 가까우며 나보다 높은 탑의 인덱스를 찾는 문제입니다.

N <= 500,000 이므로 NlogN이하의 시간복잡도를 가져야 합니다. 그렇기 때문에 마지막에서 처음까지 가장 가까운 탑을 찾는 방법인 브루트포스는 N^2의 시간복잡도를 가져 사용할 수 없습니다.

또, 크기 <= 100,000,000이므로 각 탑의 높이를 인덱스로 리스트에 접근하는 방식도 사용할 수 없습니다.

따라서 스택을 사용하는데, 방식은 다음과 같습니다.

1. 스택의 top이 현재 보고 있는 타워보다 클때 까지 pop, 모두 현재 타워의 인덱스 번호를 답으로 지정한다.
2. 현재 타워를 스택에 push한다.
3. 모든 타워를 확인할 때까지 반복한다.

1번 과정에서 스택에는 현재 보고있는 타워보다 큰 수밖에 남지 않으며, 시간복잡도를 만족하게 됩니다.

---

풀이 코드

n = int(input())
tower = list(zip(map(int, input().split()), [i for i in range(n)]))
stack = []
answer = [0] * n
for i in range(n - 1, -1, -1):
    while stack:
        ele, index = stack.pop()
        if tower[i][0] > ele:
            answer[index] = i + 1
        else:
            stack.append([ele, index])
            break
    stack.append(tower[i])
for x in answer:
    print(x, end=" ")

---