[Python/Programmers] 뒤에 있는 큰 수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한 사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

풀이

Code

def solution(numbers):
    answer = []
    # 1. 리스트 뒤집기
    numbers = numbers[::-1]
    # 2. 스택 생성
    stack = []
    # 3.
    for num in numbers :
        # 3-1.
        while True :
            # 3-1-1. 스택이 비어있을 경우
            if not stack :
                # 출력 리스트에 -1 삽입
                answer.append(-1)
                # 스택에 현재 수 삽입
                stack.append(num)
                break
            # 3-1-2. 스택의 마지막 값이 현재 값보다 클 경우
            elif stack[-1] > num :
                # 출력 리스트에 스택의 마지막 값 삽입
                answer.append(stack[-1])
                # 스택에 현재 수 삽입
                stack.append(num)
                break
            # 3-1-3. 스택의 마지막 값이 현재 값보다 같거나 작을 경우
            else :
                stack.pop()
    return answer[::-1]