[백준/17289/파이썬] 오큰수

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

17298번: 오큰수

조건

• 크기가 N인 수열 A=a1,a2 - - - An 이 있음.
• 오큰수 NGE(i)를 구하려고 합니다.
• An의 오큰수는 An보다 오른쪽에 있으면서, Ai보다 큰 수 중, 가장 왼쪽에 있는 수를 의미합니다.
• 그러한 수가 없는 경우에, 오큰수는 -1 입니다.

입력

첫째 줄에는 수열 A의 크기 N (1≤N≤10*6)이 주어집니다.둘째 줄에는 수열 A의 원소 A1,A2...An이 주어집니다.

SOl)

처음으로 떠오르는 방법은, 배열에 넣어서, 다음 idx ~ 끝까지 하나하나 탐색하는 거지만,

그러면 , O(N^2)이 나오기 때문에, 안됨 . 지금 입력이 10^6이라서, 1억개 =1초.

시간 제한은 1초임. 그럼 다른 방법을 쓰라는건데.

이런 생각은 어떨까 ? stack을 이용해서, push,pop을 하면서 , 다음 배열 중, 어떤 수를 통제할 수 있을거 같음.

input 4 5 2 1 8 이 있다고 합시다.

stack에 자료들을 하나씩 넣고 , 들어올 수랑 TOP이랑 비교해서, TOP보다 작으면, stack에 넣고, TOp보다 크면, 바로 pop해서 stack을 비워주면됨.!!

• if stack[-1] < Input : POP until stack is empty
• elif stack[-1] > input : stacking input

그리고, 해당 값을 ans에 저장해주면 될듯합니다.

tk=[]

n =int(input())
numbers=list(map(int,input().split()))
ans =[-1]*n
# 답을 -1로 정해놓고, 아닌 것만 값을 update해주는 방식으로 합시다!
#이렇게 입력을 받고
#

for i in range(n):
	while stk and (stk[-1][0] < number[i]):
			value,idx = stk.pop()
			ans[idx] = number[i]
	stack.append(numbers[i],idx)
# 스택에 넣어줄때, ans에 답을 입력해줄 , idx도 같이 저장하면 빠르게 할 수 있음.
# (이건 구글링하면서 알아냄!)
# while문은 stk이 비거나, stk의 탑이 입력받은 값보다 클때 까지 반복을 함.
print(ans)