자신보다 오른쪽에 있는 수 중에서 자신보다 크고 가장 자신과 가까이 있는 수를 찾는 문제이다. 2중 for문을 써서 문제를 풀 수는 있지만, 범위가 1,000,000까지이기 때문에, 시간초과가 뜰 것이다.
자신의 오른쪽을 탐색할 때, 자신보다 큰 경우가 나오면 반복을 멈추고 그 값을 넣어주면 되고, 자신보다 작은 수가 나오면, 그 값들을 스택에 저장한 뒤에 큰 수가 나오면 pop해서 큰 수를 ans에 저장하면 되겠다. 하지만 스택에 값을 push하기엔 그 값들에 따른 ans값에 저장을 해줄 수가 없기 때문에, 스택에 자신보다 작은 수가 아닌 그 수의 인덱스를 push하고 인덱스를 pop해주면 된다.
##함수 선언 부분
##변수 선언 부분
A = []
stack = []
ans = []
top = -1
##메인 함수 부분
if __name__ == "__main__":
N = int(input())
A = [int(x) for x in input().split()]
ans = [-1] * N #ans배열은 모두 -1로 초기화
for i in range(N):
while (top != -1) and (A[i]>A[stack[top]]): #스택이 비어있지 않고, 스택의 top이 가리키는 인덱스의 A값이
ans[stack.pop()] = A[i] #현재 탐색하는 인덱스의 A값보다 작으면, A[i]값을 스택의 top이 가리키는 인덱스의 값을 pop해서 나온 인덱스의 ans에 넣어준다.
top -= 1
stack.append(i) #탐색중인 값이 더 작으면 인덱스를 push해준다.
top += 1
print(*ans)자신보다 작은 값을 스택에 넣어주는 것은 알아챘지만, 그 값의 인덱스를 넣어줘야한다는 생각을 하지 못해 시간을 많이 썼다. 이 문제가 스택과 관련된 문제임을 몰랐으면 시간이 훨씬 더 걸렸을 것 같다.
