[백준/Python] 2493 탑

코드

n = int(input())
arr = list(map(int, input().split()))
answer = [0] * n
stack = []

for i in range(n-1,-1,-1):
    while stack and stack[-1][1] < arr[i]:
        answer[stack[-1][0] - 1] = i + 1
        stack.pop()
    stack.append((i+1, arr[i]))

print(*answer)

기록할 점

• N이 매우 크다. stack을 사용했다.
• 뒤에서부터 순회하되 스택의 맨 위의 값이 본인보다
  - 크다면 스택에 인덱스와 값을 함께 넣어준다
  - 작다면 빼준다 (while문으로 조건에 맞다면 계속 반복)
  answer배열을 스택에서 뺀 값의 인덱스에 맞게 초기화 해준다
• 오큰수 문제와 유사하다
• 처음에 풀었는데 안돼서 6 / 9 4 6 3 7 8 이라는 반례로 아예 다시 풀어봤다