백준 17298
오큰수 구하기.
- 크기가 N인 수열 A = A1, A2, ..., AN이 있다.
- Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
- 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
- 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
입출력
| 입력 | 출력 |
|---|---|
| 4 3 5 2 7 | 5 7 7 -1 |
| 4 9 5 4 8 | -1 8 8 -1 |
접근 방식
: 이중 for문으로 i번째 원소와 i+1:의 원소를 비교하여 i번째 원소보다 큰 원소가 있다면 flag를 증가시켜주고 break문으로 빠져나간다. flag가 0이면 i번째 원소보다 큰 원소가 없는 것이므로 -1을 프린트하고, 0이 아니면 비교했던 수를 프린트한다.
사이즈가 1,000,000이기 때문에 시간초과 예상. 런타임에러(네임에러) 발생 O(N^2)
알게된 점
스택, 정확히는 스택의 pop()을 사용하면 시간이 단축된다. O(N)
- 오큰수를 구해야 할 숫자(혹은 오큰수를 구하지 못한 숫자)를 스택에 넣는다.
- 스택의 top과 배열의 i번째 원소를 비교. i번째 원소가 오큰수라면 스택에서 pop. pop한 원소의 인덱스에 해당하는 result 값에 i번째 원소를 셋팅.
코드
n = int(input())
arr = list(map(int, input().split()))
result = [-1]*len(arr)
stack = []
for i in range(len(arr)):
while stack and stack[-1][0] < arr[i]:
v, j = stack.pop()
result[j] = arr[i]
stack.append((arr[i], i))
print(*result)