Monotone stack

설명

모노톤 스택(Monotonic Stack)은 주어진 배열에서 각 원소에 대해 다음에 올 원소를 찾거나,

또는 이전에 올 원소를 찾는 데에 사용되는 자료 구조이다.

주로 "더 큰 원소를 찾아라" 또는 "더 작은 원소를 찾아라"와 같은 상황에서 유용하게 활용된다.

 

모노톤 스택의 두 가지 유형:

1. 단조 증가 스택 (Increasing Monotonic Stack): 스택에 원소를 추가할 때, 스택의 맨 위에 있는 원소보다 큰 값을 가진 원소만 추가한다. 이 스택은 "더 큰 원소를 찾아라"와 같은 상황에서 사용된다.
2. 단조 감소 스택 (Decreasing Monotonic Stack): 스택에 원소를 추가할 때, 스택의 맨 위에 있는 원소보다 작은 값을 가진 원소만 추가한다. 이 스택은 "더 작은 원소를 찾아라"와 같은 상황에서 사용된다.

모노톤 스택은 주로 스택의 맨 위에 있는 원소가 현재 처리 중인 원소에 대한 정보를 제공하면서, 불필요한 반복을 피하고 효율적으로 원하는 정보를 찾을 수 있도록 도와준다. 

 

활용 문제:

프로그래머스 LV2 - 뒤에 있는 큰 수 찾기

def solution(numbers):
    stack = []          # 모노톤 스택을 사용할 스택
    answer = [-1] * len(numbers)  # 각 원소에 대한 답을 저장할 배열 초기화

    for i in range(len(numbers)):
        # 현재 원소보다 작은 값을 가진 스택의 원소들을 처리
        while stack and numbers[stack[-1]] < numbers[i]:
            idx = stack.pop()  # 스택의 가장 위에 있는 인덱스를 꺼내옴
            answer[idx] = numbers[i]  # 해당 인덱스에 대한 답 갱신
        stack.append(i)  # 현재 인덱스를 스택에 추가

    return answer

1. stack은 모노톤 스택으로, 각 원소의 인덱스를 저장한다. 스택의 맨 위에 있는 원소가 가장 큰 값을 가진 원소에 대한 인덱스이다.
2. answer는 각 원소에 대한 답을 저장할 배열. 초기에는 모든 값이 -1로 초기화.
3. 배열을 왼쪽에서 오른쪽으로 순회하면서 각 원소에 대해 다음으로 큰 값을 찾는다.
4. 현재 원소가 스택의 맨 위에 있는 인덱스에 해당하는 원소보다 크다면, 스택의 원소를 꺼내면서 해당 인덱스에 대한 답을 갱신한다. 이를 반복하여 현재 원소보다 작은 값을 가진 스택의 원소들을 처리한다.
5. 현재 원소의 인덱스를 스택에 추가한다. 스택은 각 원소에 대한 "다음으로 큰 수를 찾기 위한 인덱스"를 저장하고 있다.

이러한 방식으로 스택을 사용하여 각 원소에 대해 다음으로 큰 값을 찾아내고, 결과를 answer 배열에 저장한다.