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이 n개 들어있는 정답을 만들어 준다.
stack에 처음숫자를 넣고 (스택에 추가할때 속도를 위해 원소값과 원소의 자릿값을 같이 묶어 넣는다)
a의를 for i in range(len(a))로 돌리면서, 만일 a[i]가 stack[-1]보다 작다면 스택에 넣고, (스택의 마지막수보다 작다면 스택의 모든 원소보다 작다), 크다면 stack이 비거나 stack[-1]이 a[i]보다 작을때까지
정답[stack에 들어있는 원소의 자릿값]을 a[i]로 바꿔준다.
이후 [a[i],i] 즉 원소와 자릿값을 stack에 추가시킨다.
n=int(input())a=list(map(int,input().split()))b=[-1]*nstack=[]
for i in range(len(a)): while stack and stack[-1][0]<a[i]:
q,r=stack.pop() #q는 원소, r은 자릿값 b[r]=a[i]
stack.append([a[i],i]) #a의 원소와 자릿값print(*b)