[백준] 오큰수

문제

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

17298번: 오큰수

---

풀이

import sys
input = sys.stdin.readline

n = int(input())
ans = [-1] * n
a = list(map(int, input().split()))
stack = []

for i in range(n):
    while stack and a[stack[-1]] < a[i]:    # 스택이 비어있지 않고, 현재 수열이 스택 top 보다 클 경우
        ans[stack.pop()] = a[i]
    stack.append(i)

print(*ans)

 

---

설명

- O(N^2) 이 될 수 있는 문제를 스택을 이용해 O(N)에 가깝게 한다는게 포인트!

- 스택에 새로 들어오는 수가 top에 존재하는 수 보다 크면 그 수는 오큰수가 된다

 

1. 스택은 값이 아닌 '인덱스'를 저장해야 한다는 것을 오랜 삽질 후에 깨달았다.

2. 기본적으로 오큰수가 없으면 -1을 출력해야 하므로 정답 배열 ans을 -1로 초기화해준다.

3. 입력받은 수들 배열 arr을 탐색

  3-1. stack이 비어있지 않고, a[스택 맨위]가 a[i]보다 작으면 반복

    3-1-1. ans의 stack.pop()한 인덱스 자리에 a[i]를 넣는다.

  3-2. stack에 i를 넣는다.

5. 꿀팁인데, 파이썬에서 배열을 print할 때, 앞에 *을 붙여주면 공백을 기준으로 원소들만 나열된다.