스택을 활용하여 효율적으로 해결할 수 있는 문제

각 원소에 대해 뒤에 있는 큰 수를 찾기 위해,
스택을 이용하여 현재 원소보다 큰 수를 찾는 방법이 효과적임

주요 로직

배열을 오른쪽에서 왼쪽으로 탐색
스택을 사용하여 현재 원소보다 큰 수를 찾는다.
스택에 들어갈 때는 현재 원소를 스택에 추가
만약 스택의 맨 위 원소가 현재 원소보다 작거나 같다면, 스택에서 제거
스택이 비어 있으면 뒷 큰수는 -1이고,
그렇지 않으면 스택의 맨 위 원소가 뒷 큰수임

O(n) 시간 복잡도로 해결할 수 있어 큰 입력에서도 효율적으로 작동

def solution(numbers):
    n = len(numbers)
    answer = [-1] * n  # 결과 배열 초기화
    stack = []  # 스택 초기화
    
    for i in range(n - 1, -1, -1):  # 배열을 오른쪽에서 왼쪽으로 탐색
        while stack and stack[-1] <= numbers[i]:  # 스택의 맨 위가 현재 수보다 작거나 같으면 제거
            stack.pop()
        
        if stack:  # 스택이 비어있지 않다면
            answer[i] = stack[-1]  # 뒷 큰수는 스택의 맨 위
        
        stack.append(numbers[i])  # 현재 수를 스택에 추가
    
    return answer