🔅코딩테스트 공부🔅/❗백준
[백준] 17298번 오큰수(python)
윤무무
2023. 3. 7. 00:16
https://www.acmicpc.net/problem/17298
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
1. 난이도 골드 4
2. 문제 해결 방법
시간초과, 메모리초과 난사로 멸망당하고 구글링을 해서 풀었다.
answer이라는 배열을 -1로 모두 저장해놓은 후,
stack에 값이 있고, num[index] > stack[top] 인 경우 인덱스를 이용해 정답 배열에 오큰수를 저장한다.
위의 과정이 끝나면
현재 인덱스를 스택에 저장하고 다음 인덱스로 넘어간다.
import sys
input = sys.stdin.readline
n = int(input().rstrip())
num = list(map(int, input().rstrip().split()))
answer = [-1] * n
stack = []
for i in range(n):
while stack and num[stack[-1]] < num[i]:
answer[stack.pop()] = num[i]
stack.append(i)
for i in answer[:-1]:
print(i, end=" ")
print(answer[-1])