알고리즘 기초 1/2 201-자료구조(연습): 오큰수

오큰수(python 17298)

첫 풀이

import sys

N = int(input())
A = sys.stdin.readline().split()
result = []
l = len(A)

for i in range(l):
    a = A.pop(i)
    if a >= min(A):
        result.append('-1')
    else:
        for j in A:
            if a < j:
                result.append(j)
                break
print(" ".join(result))

생각보단 쉽다고 생각했으나, 역시나 시간초과로 오답.
for문을 2중으로 써서 O(N&2)의 시간복잡도라서 그런듯하다

정답풀이

import sys

N = int(input())
A = list(map(int, sys.stdin.readline().split()))
answer = [-1] * N
stack = []

stack.append(0)
for i in range(1, N):
    while stack and A[stack[-1]] < A[i]:
        answer[stack.pop()] = A[i]
    stack.append(i)

print(*answer)

스택에 아직 오큰수를 찾지 못한 인덱스를 저장해둔다는 발상으로 시작
오큰수가 없을 수 있으므로 답안을 [-1]로 초기화해놓고,
스택에 수가 남아 있으며 오큰수가 있는 경우 반복하며 스택을 pop해준다
오큰수를 찾았든 못찾았든 스택에는 인덱스를 계속 추가해준다

print(*변수)는 공백으로 변수를 구분하여 출력해준다고 한다.(편리하네)