#스택

프로그래머스 문제 중 스택 분류에 해당하는 풀이를 다룬다. 현재 5개의 풀이가 있다.

LeetCode 739 Daily Temperatures에서 더 따뜻한 날을 기다리는 인덱스를 단조 스택에 둔다. 현재 온도가 높아질 때 답이 확정되는 날짜들을 처리해 O(n)에 결과를 구한다.

LeetCode 155 Min Stack을 값 스택과 최솟값 보조 스택으로 구현한다. 중복된 최솟값도 처리하면서 push, pop, top, getMin을 O(1)에 수행한다.

LeetCode 20 Valid Parentheses에서 여는 괄호를 스택에 쌓고 닫는 괄호의 짝과 순서를 확인한다. 한 번 순회해 O(n) 시간과 O(n) 공간에 중첩 구조를 검증한다.

프로그래머스 주식가격에서 아직 하락 시점을 만나지 않은 인덱스를 단조 스택에 보관한다. 가격이 처음 낮아질 때 지속 시간을 확정해 모든 시점을 O(n)에 처리한다.

프로그래머스 올바른 괄호에서 여는 괄호와 닫는 괄호의 잔량을 카운터로 관리한다. 닫는 괄호가 앞서는 순간 종료하고 마지막 잔량을 확인해 O(1) 공간에 판정한다.

스택 학습 가이드

필요한 주제만 펼쳐서 스택의 동작과 활용법을 익힌다.

스택 기본 개념

스택은 가장 나중에 들어온 원소를 가장 먼저 꺼내는 LIFO 자료구조다. 책을 쌓고 위에서부터 꺼내는 모습을 떠올리면 된다.

괄호의 짝 확인, 실행 취소, 함수 호출 기록, 역순 처리처럼 가장 최근 상태를 먼저 되돌려야 하는 문제에 맞는다.

Python에서 스택 구현

Python에서는 리스트의 오른쪽 끝을 스택의 top으로 쓰면 `append`와 `pop`을 모두 평균 `O(1)`에 처리할 수 있다.

stack = []
stack.append(value)  # push
top = stack[-1]      # peek
value = stack.pop()  # pop

빈 스택에서 `pop`이나 `stack[-1]`을 실행하면 오류가 발생하므로, 제거하거나 확인하기 전에 `stack`이 비어 있지 않은지 검사해야 한다.

단조 스택

단조 스택은 스택 안의 원소가 항상 오름차순 또는 내림차순을 유지하도록 원소를 제거하는 기법이다. 현재 값이 규칙을 깨면 top을 꺼낸 뒤 현재 값을 넣는다.

각 원소는 스택에 한 번 들어가고 최대 한 번 나오므로, 반복문 안에 `while`이 있어도 전체 시간 복잡도는 보통 `O(n)`이다.

문제 조건별 스택 활용

자주 하는 실수