단조 스택(Monotonic Stack) - 프로그래머스 뒤에 있는 큰 수 찾기

프로그래머스에서 뒤의 큰 수를 찾는 문제를 푸는데,
단조 스택에 관해 잘 설명된 한국어 문서가 없어서 정리 한다.

단조 스택

오름차순 또는 내림차순으로 수가 배열되어 있는 스택을 단조 스택이라고 하며, 천장으로 갈수록 수가 작아지는 스택을 단조감소스택, 반대의 경우를 단조증가스택이라고 한다.

단조 감소 스택 예시

단조 증가 스택 예시

뒤에 있는 가장 가까운 큰 수 찾기

단조 감소 스택을 사용하여 뒤에 있는 가장 가까운 큰 수를 찾을 수 있다.
원리는 다음과 같다.

1. [1,4,5,2,3] 의 배열이 있다.
2. 빈 스택을 준비한다.
3. 배열을 순회하며 스택에 값을 넣는다.
4. 다만, 스택의 마지막 값(1)과 현재 순회중인 값(4)을 비교하여 단조 감소 스택을 만족하는지 확인하고, 만약 그렇지 않다면 마지막 값(1)의 다음으로 큰 수는 현재 순회중인 배열의 값(4)이다.

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

다음 단조 감소 스택의 내용을 바탕으로 다음 문제를 풀이해보도록 하자.

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

첫 번째 시도

def solution(numbers):
    answer = []
    for index, number in enumerate(numbers):
        is_bigger = False
        for i in range(index+1, len(numbers)):
            if number < numbers[i]:
                answer.append(numbers[i])
                is_bigger = True
                break
        
        if not is_bigger:
            answer.append(-1)
                
    return answer

현재 순회중인 배열 값과 그 이후의 배열을 모두 비교하여 정확하게 값을 구할 수 있다.
그러나, for 문을 2번 순회하기에 시간 복잡도는 n^2이 된다.

단조 감소 스택을 활용하여 풀이

def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []
    for index, number in enumerate(numbers):
        while stack and numbers[stack[-1]] < number:
            answer[stack.pop()] = number
        stack.append(index)
                
    return answer

1. answer를 -1로 초기화한다.
2. 스택에 index를 담는다.
3. 단조 감소 스택을 만족하지 않는 경우, stack[-1]의 index 값은 순회중인 배열 값이라고 판단한다.

다음과 같이 풀이를 함으로써 시간 복잡도를 n으로 대폭 줄일 수 있다.