[백준] 17298: 오큰수 (Python)

문제📖

풀이🙏

• 시간 제한이 존재하므로 모든 배열을 이중 반복문으로 하여 O(n^2)이 아닌 O(n)으로 풀기 위해 스택을 사용했다.
• 스택에 값을 넣어주는 것이 아닌 인덱스를 넣어줘서 해결한다.
• 새로운 값이 기존 스택에 있는 값을 비교하고 클 경우에 result에 새로운 값을 삽입하고 스택에 인덱스를 저장한다.
  

코드💻

num = int(input())
data = list(map(int, input().split()))
stack = []
result = [-1 for _ in range(num)]
stack.append(0)
for i in range(num):
    while data[stack[-1]] < data[i]:
        result[stack.pop()] = data[i]
    stack.append(i)

for r in result:
    print(r, end= ' ')