[백준/파이썬] 2493번 탑

 

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

2493번: 탑

문제 해석

 

주어진 배열에서 자신보다 큰 가장 좌측의 탑의 위치를 구하는 문제이다.

---

코드

 

# input
input = __import__('sys').stdin.readline
n = int(input())
arr = list(map(int, input().split()))
ans = [0] * n

stack = [(n - 1, arr[-1])]
for k in range(2, n + 1):
    c = arr[n - k]
    if c >= stack[-1][1]:
        while 1:
            a, b = stack.pop()
            ans[a] = n - k + 1
            if stack and c >= stack[-1][1]: continue
            else: 
                stack.append((n - k, c))
                break
    else:
        stack.append((n - k, c))

print(*ans)

---

문제 풀이

 

스택에는 (인덱스, 높이)를 저장한다.

주어진 배열을 거꾸로 확인하며 진행한다.

Stack의 가장 위의 수와 배열의 역순을 비교한다.

Stack의 수가 더 크다면 비교하는 값을 스택에 넣는다.

 

더 작다면 pop하고, pop한 인덱스에 현재 비교중인 값의 인덱스를 넣는다. 이후 다음 Stack의 최상단 값과 비교하고, 반복한다.