[백준] Python - 2493 탑

문제 링크

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

2493번: 탑

 

문제 풀이

1. 탑의 제일 오른쪽부터 순회하기 위해 stack에 제일 오른쪽 탑의 높이와 인덱스를 추가한다.
2. 순회하면서 현재 탑의 높이보다 왼쪽 탑이 낮다면, stack에 현재 탑도 추가해준다. 그리고 다음 왼쪽 탑과 비교하기 위해 반복문을 나온다.
3. 그렇지 않다면, stack에서 꺼낸 탑의 번호에 마주친 왼쪽 탑의 번호를 result에 추가한다. stack에 있는 요소 모두 왼쪽 탑과 비교 반복한다. 
4. 그렇게 검사를 다 하고 반복문을 나오면, 방금 비교했던 왼쪽 탑도 검사하기 위해 stack에 추가하여 위를 반복한다.

 

전체 코드

num = int(input())
tops = list(map(int, input().split()))

stack = []
stack.append((tops[-1], num-1)) 
result = [0 for _ in range(num)]

for i in range(num-2, -1, -1) :
    while stack :  
        if stack[-1][0] <= tops[i] :
            result[stack.pop()[1]] = i+1 
        else :
            stack.append((tops[i], i))
            break
    stack.append((tops[i], i)) 

print(*result)