17298번 - 오큰수

💡 리스트 초기화를 잘 이용하자!

import sys

input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split(' ')))
stack = []
ans = [-1] * N

for i in range(N):
    
    while stack:
        if arr[i] > arr[stack[-1]]:
            ans[stack.pop()] = arr[i]
        else:
            stack.append(i)
            break
        
    stack.append(i)

print(*ans)

• 시간 제한이 1초이고, N의 최대값이 1,000,000 이였다. 따라서 for문을 1번만 사용할 수 있었고, 이 경우에는 스택을 사용하였다.
• 풀이 법을 정리하자만 이와 같다.
  =>현재 값이 stack의 맨 위 값보다 크면, 현재 값보다 큰 수가 나올 때 까지, pop() 시키면서 arr[stack.pop()] 값에 현재 값을 넣어준다.
  => 현재 값이 stack의 맨 위 값보다 작으면, 그 값은 stack에 추가해준다.
• 내가 생각하는 중요 포인트는 처음에 ans를 초기화할때, -1로 초기화하는 것이다.
  => 처음에는 위 방식을 진행하고 stack에 남은 index에 대한 ans[index] 값을 -1로 지정해주려고 했지만, 이 방식은 for문을 한번 더 써야했다.
  => 따라서 처음부터 초기화할때 -1로 초기화해준다면, stack의 남은 수를 처리하지 않아도 되기 때문에, 시간 복잡도 측면에서 이득이다!!