스택·큐·덱 - 순서를 기억하는 자료구조

이 장에서 배우는 것

앞 장에서 정렬된 값이나 답의 범위를 좁히며 필요한 위치를 찾았다. 이번에는 데이터를 찾는 기준보다 데이터를 꺼내는 순서에 주목한다. 마지막에 넣은 항목을 먼저 꺼낼지, 먼저 들어온 항목부터 처리할지에 따라 프로그램이 기억해야 할 정보와 풀이 방법이 달라진다.

스택(stack)은 마지막에 넣은 것을 먼저 꺼내고, 큐(queue)는 먼저 넣은 것을 먼저 꺼낸다. 덱(deque)은 양쪽 끝에서 넣기와 꺼내기를 지원한다. 세 자료구조는 이름을 외우는 것보다 어떤 순서를 지켜야 문제의 조건이 유지되는지 이해하는 것이 중요하다.

• 괄호의 짝을 맞추며 스택이 기억하는 정보를 설명한다.
• 접수 순서와 너비 우선 탐색(BFS)에 큐가 필요한 이유를 이해한다.
• 리스트의 앞쪽 삭제 비용을 알고 상황에 맞게 deque를 사용한다.
• 단조 스택으로 다음 큰 수를 구하고 각 항목이 처리되는 횟수를 센다.
• 작은 입력을 모두 만들어 느린 정답과 빠른 풀이를 대조한다.

문제 상황

작업 관리 도구를 만든다고 하자. 입력한 작업 묶음의 괄호가 올바르게 닫혔는지 확인해야 한다. 접수된 작업은 기다린 순서대로 처리해야 한다. 하루 작업량 기록에서는 각 시점보다 작업량이 처음으로 커지는 이후 시점을 찾고 싶다. 모두 목록을 다루지만 필요한 순서는 서로 다르다.

이 장에서는 이 상황을 세 가지 짧은 문제로 나눈다. 첫째는 작업 묶음 기호 검사다. 문자열에는 소괄호와 대괄호만 들어 있으며, 모든 여는 괄호가 알맞은 종류의 닫는 괄호와 순서에 맞게 짝지어져야 한다. 빈 문자열도 올바른 기록으로 본다.

둘째는 접수 창구의 대기 목록이다. 작업이 들어오면 뒤에 붙이고, 담당자가 준비되면 앞에서 하나를 꺼낸다. 긴급 작업이라는 별도 조건은 없으며 접수 순서를 그대로 지킨다. 이 순서가 탐색에서 어떻게 쓰이는지도 짧게 살펴본다.

셋째는 시간대별 포장량 기록이다. 각 위치에 대해 오른쪽에 있으면서 현재 값보다 엄격하게 큰 값 중 가장 먼저 나타나는 값을 구한다. 이를 다음 큰 수라고 부르겠다. 값이 같은 경우는 답이 아니다. 오른쪽에 더 큰 값이 없으면 -1을 기록한다. 포장량은 0 이상의 정수이므로 -1은 실제 값과 구별된다.

예를 들어 기록이 [4, 2, 2, 5, 3, 6]이면 첫 번째 4의 답은 5다. 두 번째 2는 바로 다음 2를 건너뛰고 5를 답으로 삼는다. 마지막 6의 오른쪽에는 값이 없으므로 답은 -1이다. 완성 프로그램은 이 문제를 두 방식으로 풀고 결과를 비교한다.

가장 최근의 미완료 작업은 스택에 둔다

괄호를 왼쪽부터 읽을 때 닫는 괄호가 만나야 하는 상대는 아직 닫히지 않은 여는 괄호 중 가장 최근에 나온 것이다. 바깥 묶음보다 안쪽 묶음을 먼저 닫아야 하기 때문이다. 이처럼 나중에 시작한 일을 먼저 마쳐야 할 때 스택이 자연스럽다.

Python 리스트의 오른쪽 끝을 스택의 꼭대기로 쓰면 된다. append로 넣고 pop으로 꺼낸다. 마지막 원소를 보기만 할 때는 stack[-1]을 쓴다. 다만 빈 리스트에는 마지막 원소가 없으므로 먼저 비었는지 확인해야 한다.

작업 묶음 기록 [()]을 읽을 때 스택에는 아직 닫히지 않은 괄호가 남는다

읽은 기호	동작	처리 후 스택
시작 전	빈 스택을 준비한다	[]
[	여는 괄호를 넣는다	['[']
(	여는 괄호를 넣는다	['[', '(']
)	꼭대기의 (와 짝지어 꺼낸다	['[']
]	꼭대기의 [와 짝지어 꺼낸다	[]

여기서 유지할 불변식은 짧다. 지금까지 읽은 부분에서 아직 닫히지 않은 여는 괄호가 등장 순서대로 스택에 들어 있다. 처음에는 읽은 문자가 없으므로 성립한다. 여는 괄호는 뒤에 추가하고, 닫는 괄호는 가장 최근의 여는 괄호와 짝이 맞을 때만 제거하므로 다음 문자 뒤에도 유지된다.

닫는 괄호를 읽었는데 스택이 비었거나 꼭대기의 종류가 다르면 올바른 기록이 아니다. 끝까지 읽은 뒤 스택에 괄호가 남아 있어도 닫지 못한 묶음이 있으므로 실패다. 단순히 여는 괄호와 닫는 괄호의 개수만 세면 ([)] 같은 잘못된 순서를 구별할 수 없다.

각 문자를 한 번 읽고 각 여는 괄호를 한 번 넣고 최대 한 번 꺼내므로 길이가 n일 때 시간은 O(n)이다. 모두 여는 괄호인 입력에서는 n개가 쌓일 수 있으므로 추가 공간은 O(n)이다. 이 근거를 코드로 옮기면 다음과 같다.

def valid_brackets(text):
    stack = []
    opening = {")": "(", "]": "["}

    for ch in text:
        if ch in "([":
            stack.append(ch)
        else:
            if not stack or stack[-1] != opening[ch]:
                return False
            stack.pop()

    return not stack

이 함수의 입력은 문제에서 정한 네 종류의 괄호로 한정한다. 일반 문서에서 다른 문자까지 받으려면 무시할지 오류로 처리할지를 별도 조건으로 정해야 한다. 함수 끝의 not stack은 남은 괄호가 없을 때 True가 된다.

접수 순서를 지키는 큐와 양쪽 끝을 쓰는 덱

접수 창구에서는 먼저 기다린 작업부터 처리해야 한다. 뒤에 새 작업을 넣고 앞에서 오래된 작업을 꺼내면 이 순서가 유지된다. 이때의 불변식은 큐에 남은 작업이 접수된 순서대로 놓여 있다는 것이다. 뒤에 추가하는 동작과 앞에서 제거하는 동작 모두 남은 작업의 상대적인 순서를 바꾸지 않는다.

리스트로도 append와 pop(0)을 조합해 같은 결과를 낼 수 있다. 그러나 리스트의 첫 원소를 지우면 뒤에 있던 원소들의 참조를 앞으로 옮겨야 한다. 길이가 k인 리스트에서 pop(0)의 비용은 O(k)다. n개를 앞에서 하나씩 모두 꺼내면 옮기는 횟수가 대략 n에 비례하는 수부터 차례로 줄어들어 전체 비용이 O(n²)이 된다.

collections 모듈의 deque는 양쪽 끝의 추가와 제거를 O(1)에 지원한다. 큐로 쓸 때는 append와 popleft를 짝지으면 된다. 양쪽 끝을 모두 다루는 문제라면 appendleft와 pop도 사용할 수 있다. 이름이 비슷하므로 어느 끝에서 동작하는지 먼저 말로 확인하는 편이 좋다.

from collections import deque

waiting = deque(["작업 가", "작업 나"])
waiting.append("작업 다")

handled = []
while waiting:
    handled.append(waiting.popleft())

# handled는 ["작업 가", "작업 나", "작업 다"]다.

작업 n개를 한 번씩 넣고 꺼내면 전체 시간은 O(n)이다. 대기 중인 작업을 보관하는 공간은 최대 O(n)이다. 덱의 장점은 양 끝에서의 조작에 있다. 중간 위치를 자주 읽는 작업까지 리스트의 인덱스 접근과 같은 비용이라고 가정해서는 안 된다.

큐는 너비 우선 탐색에서도 쓰인다. 출발점에서 한 번에 갈 수 있는 곳을 먼저 처리하고, 그다음 두 번에 갈 수 있는 곳을 처리하는 식이다. 아직 처리하지 않은 장소를 큐의 뒤에 넣으면, 먼저 발견한 가까운 장소가 앞에서 먼저 나온다. 모든 이동 비용이 같다는 조건에서 이 순서가 이동 횟수가 작은 장소부터 처리하도록 만든다.

예를 들어 출발 장소에서 가와 나를 발견하고, 가에서 다를 발견했다고 하자. 가를 꺼낸 뒤 다를 뒤에 넣으면 큐는 [나, 다]가 된다. 나보다 다를 먼저 처리하지 않으므로 같은 거리의 장소를 건너뛰지 않는다. 그래프의 표현과 전체 탐색 구현은 그래프 탐색을 다룰 때 살펴본다. 여기서는 먼저 발견한 항목부터 꺼내는 순서를 큐가 보장한다는 점에 집중한다.

같은 장소를 여러 경로로 발견할 수 있다면 큐에 넣는 순간 방문 여부를 표시해야 중복 등록을 막을 수 있다. 큐에서 꺼낼 때까지 표시를 미루면 그 사이 다른 장소가 같은 항목을 다시 넣을 수 있다. 큐의 순서와 중복 방지는 서로 다른 역할이다.

다음 큰 수를 기다리는 단조 스택

다음 큰 수의 가장 직접적인 풀이는 각 위치에서 오른쪽으로 걸어가며 처음 만나는 큰 값을 찾는 것이다. 조건을 그대로 옮기므로 느린 정답 함수로 쓰기 좋다. 하지만 값이 계속 작아지는 기록에서는 어느 위치에서도 큰 값을 찾지 못해 끝까지 확인한다. 비교 횟수는 (n - 1) + (n - 2) + … + 1이 되어 O(n²)이다.

시선을 바꿔 현재 값이 누구의 답이 되는지 생각한다. 아직 답을 찾지 못한 위치들을 스택에 넣어 둔다. 새 값이 스택 꼭대기의 값보다 크면 그 위치의 답을 지금 확정한다. 새 값이 그 아래의 값보다도 크면 계속 꺼내며 답을 채운다. 그 뒤 현재 위치를 스택에 넣어 자신의 답을 기다리게 한다.

스택에는 값 대신 인덱스를 넣는다. 답을 원래 위치에 기록해야 하고 같은 값이 여러 번 나올 수도 있기 때문이다. 인덱스를 보관하면 원래 값은 values[인덱스]로 확인할 수 있다. 이 문제의 스택은 아래에서 위로 값이 커지지 않는 순서를 유지한다. 이런 식으로 값의 한 방향 순서를 유지하는 스택을 단조 스택(monotonic stack)이라고 한다.

기록 [4, 2, 2, 5, 3, 6]에서 큰 값이 도착하면 기다리던 위치의 답이 정해진다

현재 위치와 값	이번에 확정한 답	처리 후 스택: 위치(값)
0번, 4	없음	0(4)
1번, 2	없음	0(4), 1(2)
2번, 2	없음	0(4), 1(2), 2(2)
3번, 5	2번 → 5, 1번 → 5, 0번 → 5	3(5)
4번, 3	없음	3(5), 4(3)
5번, 6	4번 → 6, 3번 → 6	5(6)

불변식은 두 부분이다. 첫째, 스택의 인덱스는 아래에서 위로 증가하고 그 값은 커지지 않는다. 둘째, 스택에 남은 각 위치는 지금까지 읽은 오른쪽 구간에서 자신보다 큰 값을 아직 만나지 못했다. 시작할 때 빈 스택이므로 두 조건이 성립한다.

현재 값보다 작은 꼭대기를 꺼낼 때 그 위치는 이전까지 더 큰 값을 만나지 못했다. 따라서 현재 값은 오른쪽에서 처음 나타난 큰 값이다. 꼭대기를 꺼내는 동안에도 다른 미해결 위치의 순서는 유지된다. 반복을 마치면 꼭대기의 값은 현재 값 이상이거나 스택이 비어 있다. 여기에 현재 인덱스를 넣으므로 값이 커지지 않는 순서도 유지된다.

끝까지 남은 위치는 오른쪽에 큰 값이 없었던 위치다. 답 배열을 처음부터 -1로 채워 두면 이 위치들을 별도로 처리할 필요가 없다. 같은 값은 큰 값이 아니므로 반복 조건은 <다. 같은 값을 만났을 때 꺼내지 않는 이유가 여기에 있다.

코드에는 for 안에 while이 들어가지만 전체 시간은 O(n)이다. 각 인덱스는 정확히 한 번 들어가고 최대 한 번 나온다. 어떤 시점에 많이 꺼냈다면 그것은 앞선 시점에 쌓아 둔 인덱스들이다. 모든 시점의 꺼내기 횟수를 더해도 n을 넘지 않는다. 답 배열과 스택이 각각 최대 n개를 저장하므로 공간은 O(n)이다.

이제 구현하고 작은 입력을 전수 대조한다. 가능한 값을 0, 1, 2로 정하고 길이 0부터 7까지의 모든 기록을 만든다. 같은 값, 오름차순, 내림차순, 빈 기록 등이 함께 들어간다. 입력 수는 1 + 3 + 3² + … + 3⁷ = 3,280개다. 전수 대조가 모든 길이에 대한 증명은 아니지만 경계 조건이나 비교 기호의 실수를 찾는 데 도움이 된다.

완성 코드

다음을 main.py로 저장한다. 표준 라이브러리만 사용하며 외부 입력을 기다리지 않는다. 코딩 테스트에서 줄 단위로 읽는 상황은 io.StringIO에 준비한 문자열을 넣어 흉내 낸다. 난수를 사용하지 않으므로 실행할 때마다 같은 입력을 검사하고 같은 결과를 출력한다.

import io
from itertools import product


def next_greater_slow(values):
    answer = [-1] * len(values)
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[j] > values[i]:
                answer[i] = values[j]
                break
    return answer


def next_greater_fast(values):
    answer = [-1] * len(values)
    stack = []
    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            previous = stack.pop()
            answer[previous] = value
        stack.append(i)
    return answer


def read_example():
    source = io.StringIO("6\n4 2 2 5 3 6\n")
    n = int(source.readline())
    values = list(map(int, source.readline().split()))
    if n < 0 or len(values) != n:
        raise ValueError("기록 개수가 맞지 않는다.")
    if any(value < 0 for value in values):
        raise ValueError("포장량은 0 이상이어야 한다.")
    return values


def verify_all():
    checked = 0
    for length in range(8):
        for items in product(range(3), repeat=length):
            values = list(items)
            expected = next_greater_slow(values)
            actual = next_greater_fast(values)
            if actual != expected:
                raise AssertionError(
                    f"대조 실패: {values}, {expected}, {actual}"
                )
            checked += 1
    return checked


def main():
    values = read_example()
    slow = next_greater_slow(values)
    fast = next_greater_fast(values)
    if slow != fast:
        raise AssertionError("예시 결과가 다르다.")
    checked = verify_all()

    print("포장량:", *values)
    print("느린 풀이:", *slow)
    print("단조 스택:", *fast)
    print(f"전수 대조: {checked}개 통과")


if __name__ == "__main__":
    main()

줄별 해설

import io는 문자열을 파일처럼 읽기 위한 준비다. from itertools import product는 짧은 기록의 모든 조합을 차례로 만드는 도구를 가져온다. 둘 다 Python에 포함되어 있어 따로 설치할 필요가 없다.

next_greater_slow의 첫 줄은 입력 길이와 같은 답 배열을 -1로 채운다. 바깥 반복의 i는 답을 구할 위치다. 안쪽 반복의 j는 그 바로 오른쪽인 i + 1부터 시작한다. 더 큰 값을 만나면 답을 기록하고 break로 멈춘다. 멈추지 않으면 더 뒤에 있는 큰 값으로 답이 덮여서 ‘처음’이라는 조건을 잃는다.

next_greater_fast도 같은 답 배열로 시작한다. stack = []에는 아직 답이 없는 인덱스를 모은다. enumerate(values)는 현재 인덱스 i와 값 value를 함께 준다. 값만 있으면 정답 배열의 어느 칸을 채워야 하는지 알기 어려우므로 두 정보를 함께 사용한다.

while stack and values[stack[-1]] < value:는 먼저 스택이 비지 않았는지 확인한다. Python의 and는 앞 조건이 거짓이면 뒤 조건을 평가하지 않으므로 빈 스택에서 마지막 원소를 읽지 않는다. stack[-1]은 기다리는 인덱스이고, 이를 다시 values의 인덱스로 사용해 그 위치의 값을 얻는다.

previous = stack.pop()은 답을 찾은 위치를 꺼낸다. 이어지는 answer[previous] = value가 그 위치의 답을 채운다. while을 다 마친 뒤의 stack.append(i)는 현재 위치를 새 대기자로 등록한다. 현재 위치를 먼저 넣으면 꼭대기가 자기 자신이 되어 필요한 비교가 진행되지 않는다.

read_example의 문자열에서 첫 줄은 개수, 둘째 줄은 기록이다. readline()은 한 줄을 읽고, split은 공백을 기준으로 나누며, map과 int가 각각의 조각을 정수로 바꾼다. 개수와 값의 범위 검사는 예시 데이터가 문제의 조건을 만족하는지 확인한다. 이 입력 형식에서는 기록을 둘째 줄 한 줄에 둔다.

verify_all의 range(8)은 길이 0부터 7까지를 만든다. product(range(3), repeat=length)는 각 칸에 0, 1, 2를 넣는 모든 경우를 생성한다. 길이가 0일 때도 빈 기록 한 개가 만들어진다. 각 기록을 두 함수에 넣고 결과가 다르면 입력과 두 결과를 포함한 오류를 일으킨다.

checked += 1은 대조가 끝난 경우만 센다. 따라서 반환값은 성공적으로 비교한 입력 수다. 검사를 assert 문으로만 작성하지 않고 명시적인 조건과 raise로 작성했으므로, 최적화 실행 옵션 때문에 검사가 생략되는 일도 없다.

main은 예시 결과의 일치 여부와 전수 대조를 확인한 뒤 출력한다. print의 별표는 리스트 원소를 각각의 인자로 펼쳐 공백으로 구분해 출력하게 한다. 마지막 조건문은 이 파일을 직접 실행했을 때 main을 호출한다.

실행 결과

macOS나 Linux의 터미널에서 파일을 저장한 디렉터리로 이동한 뒤 다음 명령을 실행한다. 첫 명령은 문법을 검사하고, 둘째 명령은 예시와 전수 대조를 실행한다.

python3 -W error -m py_compile main.py
python3 main.py

문법 검사에 성공하면 첫 명령은 아무것도 출력하지 않는다. 프로그램의 예상 출력은 다음과 같다.

포장량: 4 2 2 5 3 6
느린 풀이: 5 5 5 6 6 -1
단조 스택: 5 5 5 6 6 -1
전수 대조: 3280개 통과

완성 코드의 빠른 함수는 입력 길이에 비례하는 시간에 동작한다. 전수 대조 프로그램 전체의 실행 시간은 검사한 모든 입력의 길이와 느린 풀이의 작업량까지 합한 값이다. 검증 코드의 비용과 실제 풀이 함수의 복잡도를 구분해야 한다. 여기서는 길이를 7까지로 제한해 느린 함수도 부담 없이 정답 기준으로 사용한다.

실무에서 자주 틀리는 것

큐의 앞쪽을 리스트로 계속 지운다

다음 코드는 접수 순서 자체는 지키지만 작업이 많이 쌓였을 때 앞쪽 삭제 비용이 커진다.

waiting = list(range(100))
while waiting:
    current = waiting.pop(0)

앞에서 반복해서 꺼내는 용도라면 덱으로 바꾼다. 초기 목록을 덱으로 만드는 비용은 O(n)이지만 이후 각 꺼내기는 O(1)이다.

from collections import deque

waiting = deque(range(100))
while waiting:
    current = waiting.popleft()

괄호를 꺼낸 뒤에 빈 스택을 확인한다

닫는 괄호가 먼저 나오는 기록에서는 pop 자체가 실패한다. 꺼낸 뒤 확인하는 방식으로는 이를 막을 수 없다.

# ch는 닫는 괄호이고 opening은 짝을 담은 딕셔너리다.
top = stack.pop()
if top != opening[ch]:
    return False

비어 있는지 먼저 확인하고, 종류까지 맞을 때 꺼낸다. 조건식의 순서에도 의미가 있다.

if not stack or stack[-1] != opening[ch]:
    return False
stack.pop()

같은 값까지 다음 큰 수로 처리한다

다음 조건은 같은 값도 답으로 확정한다. 입력 [2, 2]에서 앞의 2에 대한 답이 2가 되어 조건을 어긴다.

while stack and values[stack[-1]] <= value:
    answer[stack.pop()] = value

엄격하게 큰 값을 구하므로 작은 값만 꺼낸다. 고친 코드에서 [2, 2]의 두 위치는 모두 -1로 남는다.

while stack and values[stack[-1]] < value:
    answer[stack.pop()] = value

한 번만 꺼내거나 현재 위치를 먼저 넣는다

현재 값 하나가 여러 위치의 답이 될 수 있으므로 if로 한 번만 꺼내면 부족하다. 아래 코드는 5가 도착했을 때 기다리는 값 중 하나만 해결한다.

if stack and values[stack[-1]] < value:
    answer[stack.pop()] = value
stack.append(i)

조건이 유지되는 동안 반복해서 꺼낸 뒤 현재 위치를 넣는다. 반복 전에 현재 위치를 넣는 것도 잘못이다. 자신과 자신을 비교하게 되어 이전 대기자를 처리하지 못한다.

while stack and values[stack[-1]] < value:
    answer[stack.pop()] = value
stack.append(i)

한눈에 보기

필요한 처리 순서에 따라 자료구조와 연산을 고른다

용도	저장하는 정보	주요 연산	비용
괄호 검사	미완료 여는 괄호	리스트 append, pop	전체 O(n)
접수 순서 처리	대기 중인 작업	덱 append, popleft	작업당 O(1)
양쪽 끝 처리	앞뒤로 조작할 항목	덱의 양 끝 추가·제거	연산당 O(1)
다음 큰 수	미해결 인덱스	단조 스택 추가·제거	전체 O(n)
리스트 앞쪽 삭제	순서가 있는 항목	pop(0)	길이 k에서 O(k)

리스트 끝의 append는 저장 공간을 늘리는 시점을 포함해 여러 번의 연산을 합쳐 보면 한 번당 평균 O(1)이다. 단조 스택에서도 한 순간의 반복 횟수만 보지 않고 입력 전체에서 각 인덱스가 들어가고 나오는 횟수를 센다. 두 경우 모두 전체 작업량을 기준으로 비용을 판단한다.

풀이를 시작할 때는 ‘무엇을 저장할까’와 함께 ‘어느 항목을 다음에 꺼내야 할까’를 묻는다. 최근의 미완료 항목이면 스택, 오래 기다린 항목이면 큐, 양쪽 끝을 모두 조작해야 하면 덱이 후보가 된다. 다음 장에서는 순서보다 값 자체를 기준으로 세거나 찾는 상황을 다룬다.

연습 문제

1. 작업 묶음 기록 [](()), ([)], ]의 유효성을 각각 판단하라. 잘못된 기록은 어느 문자를 읽을 때 실패하는지 설명하라.
2. 포장량이 [3, 1, 1, 4, 2]일 때 다음 큰 수 배열을 구하라. 값 4를 읽기 직전과 직후의 스택을 인덱스로 적어라.
3. 다음 큰 수 대신 오른쪽에서 처음 나타나는 ‘현재 값 이상인 수’를 구하려 한다. 빠른 함수의 어느 조건을 바꿔야 하는지 쓰고 [2, 2, 1]의 결과를 구하라. 느린 함수에도 같은 변경을 반영하라.
4. 접수 목록에 가, 나를 넣고 앞에서 하나를 처리한 뒤 다를 넣는다. 남은 작업의 처리 순서를 쓰고 deque 코드로 표현하라. 앞에서 꺼내는 popleft를 pop으로 바꾸면 결과가 어떻게 달라지는지도 설명하라.

정답과 해설

괄호 검사

[](() )에서 공백을 뺀 기록인 [](() )를 눈으로만 읽으면 혼동하기 쉽다. 문제의 실제 기록 [](()), 즉 [, ], (, (, ), )의 여섯 기호를 차례로 처리하면 스택이 마지막에 비므로 유효하다. ([)]는 세 번째 기호인 )를 읽을 때 꼭대기가 [이므로 실패한다. ]는 첫 기호를 읽을 때 스택이 비어 있으므로 실패한다.

첫 기록은 앞의 []가 먼저 끝나고, 뒤의 (())가 별도로 끝나는 구조다. 묶음이 연속해서 나타나도 각각 올바르게 닫히면 전체 기록은 유효하다.

다음 큰 수와 스택 추적

정답은 [4, 4, 4, -1, -1]이다. 4를 읽기 직전 스택은 [0, 1, 2]이고 대응하는 값은 [3, 1, 1]이다. 4가 들어오면 인덱스 2, 1, 0의 순서로 꺼내 각각의 답을 4로 채운다. 그 뒤 현재 인덱스 3을 넣으므로 스택은 [3]이 된다.

마지막 값 2는 4보다 작으므로 인덱스 4도 스택에 남는다. 끝난 뒤 남은 두 위치에는 오른쪽의 큰 값이 없으므로 초기값 -1이 유지된다.

현재 값 이상인 수로 조건 변경

현재 값과 같은 경우도 답이므로 빠른 함수의 비교를 <에서 <=로 바꾼다. 느린 함수는 >를 >=로 바꾼다. [2, 2, 1]의 결과는 [2, -1, -1]이다. 앞의 2는 바로 다음 2로 해결되고 뒤의 두 위치는 조건에 맞는 수를 만나지 못한다.

# 빠른 함수에서 바꿀 반복 조건
while stack and values[stack[-1]] <= value:
    previous = stack.pop()
    answer[previous] = value

이 변형에서는 같은 값도 꺼내므로 스택의 값이 아래에서 위로 엄격하게 작아진다. 전수 대조를 다시 할 때는 두 함수의 조건을 함께 바꿔야 한다. 두 함수가 서로 다른 문제를 풀고 있으면 결과 불일치가 구현 오류인지 조건 차이인지 구별하기 어렵다.

접수 목록 처리

가를 먼저 처리한 뒤 남은 순서는 나, 다다. 다음 코드는 처리한 항목까지 함께 확인한다.

from collections import deque

waiting = deque(["가", "나"])
first = waiting.popleft()
waiting.append("다")
rest = []
while waiting:
    rest.append(waiting.popleft())

# first는 "가", rest는 ["나", "다"]다.

모든 popleft를 pop으로 바꾸면 처음에는 나를 꺼낸다. 이후 가 뒤에 다를 넣고 오른쪽에서 꺼내므로 남은 처리 순서는 다, 가가 된다. 같은 컨테이너를 사용해도 어느 끝에서 꺼내는지에 따라 지키는 순서가 달라진다.