[17298] 오큰수

N = int(input(""))
seq = list(map(int,input().split()))
nge_index = []
L = len(seq)
result = [-1 for i in range(L)]

### 시간 초과 ###
# for i in range(L):
#     for j in range(i,L):
#         if(seq[i] < seq[j]):
#             print(seq[j],end=" ")
#             break
#         elif j==L-1:
#             print(-1,end=" ")

for i in range(L):
    if(nge_index):
        while(nge_index and seq[i] > seq[nge_index[-1]]):
            result[nge_index.pop()] = seq[i]
        nge_index.append(i)
    else:
        nge_index.append(i)

print(*result)

단순접근하여 시간복잡도 O(n^2)를 갖는 코드를 생각했지만 역시 시간초과가 났다

 

스택을 사용해보기로 한다

1. 입력된 리스트를 반복문을 통해 앞에서부터 하나씩 스택에 push

2. 스택에 값이 존재하는 경우 스택의 최상단값과 현재 인덱스의 값을 비교한다

3. 현재 인덱스의 값이 더 클 경우 pop하고 현재 인덱스의 값으로 pop된 자리의 수를 오큰수로 업데이트한다

4. (2)번 조건이 불만족 할 때까지 (3)을 반복 진행한다

 

# 스택에 사용되는 값은 리스트의 값이 아닌 리스트의 인덱스 값으로 포인터 개념으로 이해하면 된다

# 스택이 가리키는 값들이 오름차순을 이루는 특징을 이용