[백준] 17298 오큰수 (파이썬)

문제

17298번: 오큰수

답을 보기 쉬울 것 같길래 도전했다 큰코다쳤다.

문제 자체는 이중for문으로 답 자체는 볼 순 있지만, 시간 복잡도에 걸리기때문에 시간초과가 뜬다.

그래서 stack을 이용했는데, stack 방법에서도 상다히 애를 먹었다

 

코드

정답 코드

import sys
input = sys.stdin.readline

n = int(input())

li = list(map(int, input().split()))
stack = [0]
answer = [-1] * n

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

print(*answer)

해설

반례 input  10 9 7 6 5 4 3 2 8 10 1 output 10 8 8 8 8 8 8 10 -1 -1

스택에 넣을 것은 인덱스이다. 인덱스 끼리 비교해주어야하기 때문에 stack에 0(9)을 넣고 range는 1(7)에서 시작한다.

스택의 맨 뒤 수보다 li가 클때(2 < 8) stack.pop해준 인덱스에 8을 넣는다.

후 8의 인덱스를 스택에 넣어준다.

 

실패코드

import sys
input = sys.stdin.readline

n = int(input())

li = list(map(int, input().split()))
stack = []
answer = [-1] * n


for i in range(0, n):
    stack.append(li[i])
    if len(stack) >= 2 and stack[-2] >= stack[-1]:
        continue
    else:
        for j in range(len(stack)):
            if stack[j] < li[i] and answer[j] == -1:
                answer[j] = li[i]


print(*answer)

처음부터 스택을 사용할 것이라 예상했지만 스택으로 리스트에 있는 내용을 쪼개서 가져온 다는 생각밖에 못했다.

제출 하면서도 이거 맨 반례와 같은 예시라면 거의 끝에서 가서 다 돌면 이중 for문보다 더 돌아가는거 아닐까하는 의문을 가지고 제출했었다. 그러고 질문방에서 힌트를 얻어서 코드를 고치게 되었다.