오큰수

bookmark

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

나의 풀이

시간초과

 

n = int(input())

data = list(map(int, input().split()))
right_big_number = []
for i in range(n):
    # 3 5 2 7
    popValue = data.pop(i)  # 3
    is_insert = False
    for idx, num in enumerate(data):
        if num > popValue and idx >= i:
            is_insert = True
            right_big_number.append(num)
            break

    if is_insert == False:
        right_big_number.append(-1)

    data.insert(i, popValue)
print(right_big_number)

기준 값보다 오른쪽에 있는값중에 가장 왼쪽에 있는거니깐

enumerate 통해서 index 보다 크고 값도 큰값을 찾으면 바로 break 걸어서 나오게함

기존 배열을 유지하기 위해서 data.insert 를 통해서 기존에 배열 유지

모범답안

n = int(input())
data = list(map(int, input().split()))
right_big_number = [-1] * n  # 결과를 저장할 리스트, 초기값은 -1로 설정

stack = []  # 인덱스를 저장할 스택
# 3 5 2 7 
# 오른쪽에 있는 큰 수 찾기
for i in range(n):
    # 스택에 값이있고 기준값보다 큰 경우
    while stack and data[stack[-1]] < data[i]:   
        right_big_number[stack.pop()] = data[i]
    stack.append(i) 

print(" ".join(map(str, right_big_number)))

right_big_number 값을 모두 -1로 초기화

while stack and data[stack[-1]] < data[i]:   
        right_big_number[stack.pop()] = data[i]
    stack.append(i) 

스택에 값이 있고 기준값보다 큰 경우 right_big_number 에 stack 값 pop 해서 index 넣고

현재의 data 값 넣기