[BOJ] 17298번: 오큰수 (python)

문제 링크 : https://www.acmicpc.net/problem/17298

💡 해결 방법

• 입력받은 리스트를 돌면서 하나씩 스택에 ❕인덱스❕ 삽입
• 스택의 최상위 원소와 리스트의 다음 원소 비교
  • 최상위 원소가 더 크면 다음 원소 인덱스를 스택에 넣기
  • 다음 원소가 더 크면 해당 값이 최상위 원소의 오큰수가 되므로 결과 출력 배열에 저장
• 스택에 원소 존재하면서 최상위 원소가 작으면 pop하면서 반복

(정답코드 참조..)

🖥️ 코드

import sys
from collections import deque

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
stack = deque()
result = [-1]*N

#stack.append(0)
for i in range(N):
    while stack and A[stack[-1]] < A[i]:
        result[stack[-1]] = A[i]
        stack.pop()
    stack.append(i)

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

✏️ 알고리즘 분류

• 자료구조
• 스택