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

배열의 오른쪽 큰 수 구하기

중첩 for문으로 구현하는 것을 스택을 이용해 n으로 시간복잡도를 개선할 수 있음

아래처럼 중첩 반복문을 돌리면 시간 초과됨

n = int(input())
data = list(map(int, input().split()))

result = []

for i in range(n):
    nge = 0
    for j in range(n - i):
        nge = data[i + j]
        if data[i] < data[i + j]:
            result.append(data[i + j])
            break

    if data[i] >= nge:
        result.append(-1)

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

정답 답변

n = int(input())
data = list(map(int, input().split()))

stack = []
NGE = [-1] * n

# 스택에 한 개씩 추가하기 위한 반복문
for i in range(n):
    current_value = data[i]
    # 스택의 마지막 값이 현재 값보다 크거나 같을 때까지 스택에서 pop한 뒤 오큰수로 할당
    while stack and stack[-1][1] < current_value:
        index, _ = stack.pop()
        NGE[index] = current_value
    stack.append((i, current_value))

for x in NGE:
    print(x, end=' ')