[알고리즘] 프로그래머스 - 뒤에 있는 큰 수 찾기(Python)

문제 설명

알고리즘 고민

자기 자신보다 뒤에 있는 수 중에서 가장 가까운 수로 치환하는 문제이다. 처음에는 인덱싱을 이용해서 확인하는 인덱스와 그 뒤에있는 배열을 잘라 비교하면서 해결하려 했지만 이 방법은 이중 for문을 사용하는 꼴이 되어 시간 초과 문제가 발생하였다. 따라서 스택을 사용해서 큰 수를 저장하고 확인하는 값이 스택의 마지막 값보다 크면 큰 수를 현재 숫자로 업데이트하고 이전 수를 pop으로 제거하는 방법을 통해 해결하였다.

코드

def solution(numbers):
    stack = []
    answer = [-1] * len(numbers)

    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]
        stack.append(i)
    
    return answer