[백준 파이썬] #17298. 오큰수

풀기 전 생각해보기😮

• 주어진 조건을 봤을 때 N의 크기가 1 ~ 1,000,000임을 확인할 수 있다. 시간복잡도 O(n)로 알고리즘을 짜야 시간초과 문제가 발생하지 않는다
• 단순히 for문을 사용하는 방식이나, 리스트의 뒷부분부터 탐색하는 방식이 잘 적용되지 않는다면, 자료구조를 활용하는 방법을 생각해보자

---

*다른 블로그 풀이를 보고 정리

풀이🛫

N = int(input())
A = list(map(int, input().split()))
answer = [-1] * N   # 기본값으로 -1을 세팅
stack = [0]

# 오른쪽 값이 현재 값보다 작을 때: 스택에 인덱스 값을 push
# 오른쪽 값이 현재 값보다 클 때: 스택에서 값을 pop하면서, 더 큰 값이 나올 때까지, 기준점의 오른쪽 값으로 대체
# 마지막 인덱스의 경우 스택에 쌓인 값이 없으므로 기본값으로 설정한 -1이 그대로 적용
for i in range(1, N):
    while stack and A[stack[-1]] < A[i]:
        answer[stack.pop()] = A[i]
    stack.append(i)

print(*answer)

 

핵심 정리🎁

• 자료구조 중 stack을 통해 문제를 풀었다. 원하는 값이 나올 때까지 append 혹은 pop을 해가면서 논리적으로 스택구조를 사용하는 능력을 길러야 한다.

링크💎

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

17298번: 오큰수