17928번 오큰수

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

---

아이디어

주어진 리스트 입력 거꾸로 보면서 스택에 아무것도 없으면 그 숫자를 넣고 아니라면 top이랑 비교해서 푸는 문제이다. 그림으로 표현하면 다음과 같다.

틀린 이유

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

answer = [-1]*n
stack = []
l.reverse()

for i in range(n):
    if len(stack) == 0:
        stack.append(l[i])
    elif stack[-1] > l[i]:
        answer[i] = stack[-1]
        stack.append(l[i])
    elif stack[-1] < l[i]:
        stack.pop()
        while stack:
            if stack[-1] < l[i]:
                stack.pop()
            elif stack[-1] > l[i]:
                answer[i] = stack[-1]
                break
        stack.append(l[i])

answer.reverse()
print(*answer)

시간복잡도는 정답코드랑 똑같이 O(n)이지만 더 많은 분기조건으로 시간초과가 난 것 같다. 정답 코드랑 비교했을 때 딱봐도 복잡해보인다.

---

코드

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

answer = [-1]*n
stack = []
l.reverse()

for i in range(n):
    while stack and stack[-1] <= l[i]: # l[i]보다 작거나 같으면 모두 pop
        stack.pop()
    if stack:
        answer[i] = stack[-1]

    stack.append(l[i])

answer.reverse()
print(*answer)