[프로그래머스/파이썬] 뒤에 있는 큰 수 찾기

내 풀이

def solution(numbers):
    stack = [] # 뒤에서 더 큰 수를 만날 때까지 인덱스를 쌓아둠
    answer = [-1] * len(numbers) # 만나지 못한 인덱스는 뒷 큰수가 없어 안 바뀌고 -1로 남음
    
    for i in range(len(numbers)):
    	# 스택에 인덱스가 있는 동안 + 스택 맨 위 인덱스의 숫자가 그 다음 수보다 작으면
        # 해당 인덱스의 숫자를 계속 대체
        # 스택에 아무 것도 없거나 있어도 뒷 큰수 조건에 해당하지 않으면 지나감
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]
        
		# 처음에는 아무것도 없으므로 바로 스택에 들어감
        # 다음 조건을 따지기 위해 해당 인덱스도 스택에 넣음
        stack.append(i)
    return answer

 

 

틀린 내 풀이 (82.6/100 : 시간초과)

from collections import deque


def solution(numbers):
    answer = []
    numbers = deque(numbers)
    max_num = max(numbers)
    
    while numbers:
        current_number = numbers.popleft() # 순서에 맞게 하나씩 숫자를 꺼냄
        
        if numbers: 
        	# 꺼낸 이후 남은 큐에서 가장 큰 수가 꺼낸 현재 수보다 작으면
            # 뒷 큰수는 없으므로 -1을 더하고
            # 가장 큰 수를 업데이트
            if current_number >= max_num:
                max_num = max(numbers)
                answer.append(-1)
                continue
        
        exist = False
        for num in numbers:
        	# 남은 큐를 차례로 확인하다가 뒷 큰수가 등장하면 바꾸고 break
            if current_number < num:
                answer.append(num)
                exist = True
                break
        if not exist: # 끝까지 존재하지 않는다면 -1
            answer.append(-1)
    return answer

 

메모

순서O:스택with인덱스 / 순서X:딕셔너리 > deque > list