스택 문제 풀이 기술

1. 스택의 기본 연산 (Push, Pop, Peek)

파이썬 리스트의 append()와 pop()은 모두 시간 복잡도 $O(1)$로 동작하여 스택 구현에 최적입니다.

Python

 

stack = []

# 1. 데이터 추가 (Push)
stack.append(1)
stack.append(2)
stack.append(3)

# 2. 데이터 꺼내기 (Pop)
top_element = stack.pop() # 3이 제거되고 반환됨

# 3. 최상단 데이터 확인 (Peek) - 제거하지 않고 값만 확인
if stack:
    top = stack[-1] # 리스트의 마지막 인덱스 활용

# 4. 스택이 비었는지 확인 (Empty Check)
if not stack:
    print("스택이 비어있습니다.")

---

2. 올바른 괄호 찾기 (가장 대표적인 유형)

괄호 짝 맞추기는 스택의 원리를 이해하기 가장 좋은 예제입니다. 여는 괄호를 만나면 스택에 넣고, 닫는 괄호를 만나면 스택에서 꺼내 짝을 맞춥니다.

Python

 

def is_valid_parenthesis(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack: # 닫는 괄호는 있는데 꺼낼 여는 괄호가 없는 경우
                return False
            stack.pop()
            
    return len(stack) == 0 # 모든 과정을 마쳤을 때 스택이 비어있어야 함

이 로직의 핵심은 **"가장 나중에 열린 괄호가 가장 먼저 닫혀야 한다"**는 점을 이용하는 것입니다. 단계별로 알기 쉽게 설명해 드릴게요.

---

1. 주요 로직 설명

• stack = []: 비어있는 리스트(스택)를 준비합니다. 열린 괄호들을 잠시 보관하는 용도입니다.
• 열린 괄호 (를 만날 때: 아직 짝을 찾지 못했으므로 스택에 넣습니다(append).
• 닫는 괄호 )를 만날 때:
  1. 비어있는지 확인: 스택이 비어있다면(not stack), 앞에 대응하는 (가 없다는 뜻이므로 즉시 False를 반환합니다.
  2. 짝 맞추기: 스택에 값이 있다면, 가장 최근에 들어간 ( 하나를 꺼냅니다(pop).
• 최종 확인 (len(stack) == 0): 모든 문자를 확인한 후, 스택에 남아있는 (가 없어야 완벽한 한 쌍들이었다고 판단합니다.

---

2. 코드 진행 예시

문자열 "(())"가 들어왔다고 가정해 보겠습니다.

단계	문자	동작	스택 상태	비고
1	(	append	['(']	첫 번째 열림
2	(	append	['(', '(']	두 번째 열림
3	)	pop	['(']	안쪽 괄호 쌍 완성
4	)	pop	[]	바깥쪽 괄호 쌍 완성
결과	-	True	빈 스택	성공

만약 "(()"라면 마지막에 스택에 (가 하나 남으므로 False가 됩니다.

---

3. 이 코드의 장점

1. 시간 복잡도: $O(n)$ — 문자열을 딱 한 번만 훑기 때문에 매우 빠릅니다.
2. 공간 복잡도: $O(n)$ — 최악의 경우(모두 열린 괄호일 때) 문자열 길이만큼 스택에 저장됩니다.

Tip: 만약 (), {}, [] 처럼 여러 종류의 괄호를 검사해야 한다면, dict를 사용하여 짝을 맞춰주는 방식으로 코드를 확장할 수 있습니다.

---

3. 단조 스택 (Monotonic Stack)

프로그래머스의 **"주식 가격"**이나 "뒤에 있는 큰 수 찾기" 같은 문제에서 쓰이는 고급 기술입니다. 스택 내부를 오름차순이나 내림차순 상태로 유지하며 문제를 해결합니다.

Python

 

# 예시: 다음 큰 숫자 찾기 (현재 숫자보다 뒤에 있는 숫자 중 가장 가까운 큰 수)
def find_next_greater_elements(arr):
    n = len(arr)
    answer = [-1] * n
    stack = [] # 인덱스를 저장하는 스택

    for i in range(n):
        # 스택이 비어있지 않고, 현재 숫자가 스택 top 인덱스의 숫자보다 크다면
        while stack and arr[stack[-1]] < arr[i]:
            index = stack.pop()
            answer[index] = arr[i]
        
        stack.append(i) # 현재 인덱스를 스택에 추가
    return answer

이 코드는 **"Next Greater Element (오른쪽에서 더 큰 첫 번째 수 찾기)"**라는 유명한 알고리즘 문제를 해결하는 효율적인 방식입니다. 앞서 보신 괄호 검사 코드처럼 **스택(Stack)**을 사용하지만, 여기서는 값이 아닌 **인덱스(위치)**를 저장한다는 점이 핵심입니다.

---

1. 핵심 아이디어: "대기표를 뽑고 기다리기"

이 알고리즘을 쉽게 이해하려면, 숫자들이 **"자기보다 큰 숫자가 나타나기를 기다리는 대기실"**에 들어간다고 생각하면 좋습니다.

• 스택(Stack): 아직 자기보다 큰 숫자를 만나지 못한 인덱스들이 머무는 곳입니다.
• 비교 루프 (while): 새로 나타난 숫자(arr[i])가 대기실 맨 앞(스택 top)에 있는 숫자보다 크다면, 대기 중이던 숫자의 정답을 현재 숫자로 기록하고 대기실에서 내보냅니다(pop).
• 기록 (answer): 만약 끝까지 자기보다 큰 숫자를 만나지 못하면 초기값인 -1이 유지됩니다.

---

2. 코드 진행 시뮬레이션

arr = [2, 1, 5]라는 배열이 있다고 가정해 보겠습니다.

1. i = 0 (숫자 2):
   • 스택이 비어 있으므로 인덱스 0을 넣습니다.
   • stack = [0], answer = [-1, -1, -1]
2. i = 1 (숫자 1):
   • 현재 숫자 1은 스택 top인 arr[0](값 2)보다 작습니다.
   • 인덱스 1을 스택에 넣고 기다립니다.
   • stack = [0, 1], answer = [-1, -1, -1]
3. i = 2 (숫자 5):
   • 첫 번째 비교: 현재 숫자 5는 arr[1](값 1)보다 큽니다!
     • index 1의 정답은 5가 됩니다. pop 합니다.
   • 두 번째 비교: 현재 숫자 5는 arr[0](값 2)보다도 큽니다!
     • index 0의 정답도 5가 됩니다. pop 합니다.
   • 이제 스택이 비었으므로 본인 인덱스 2를 넣습니다.
   • stack = [2], answer = [5, 5, -1]

---

3. 왜 스택에 '인덱스'를 넣나요?

값(arr[i])을 직접 넣지 않고 인덱스를 넣는 이유는 정답 배열(answer)의 어느 위치에 값을 써야 할지 알아야 하기 때문입니다. pop()을 통해 꺼낸 인덱스가 곧 정답을 적을 위치가 됩니다.

4. 성능 분석

• 시간 복잡도: $O(n)$
  • 각 원소는 스택에 딱 한 번 들어갔다가(push), 딱 한 번 나옵니다(pop). 루프 안에 while문이 있어도 전체적으로 보면 모든 원소를 한 번씩만 처리하는 셈이라 매우 효율적입니다.
• 공간 복잡도: $O(n)$
  • 정답 배열과 스택을 위한 추가 공간이 필요합니다.

---

이 방식은 주식 가격이 처음으로 떨어지는 날을 찾거나, 건물 옥상에서 오른쪽을 봤을 때 처음으로 보이는 더 높은 건물을 찾는 등의 문제에 아주 자주 쓰입니다.

---

4. 스택 활용 시 주의할 점 & 팁

1. stack[-1] 사용 전 확인: 스택이 비어있을 때 stack[-1]을 호출하면 IndexError가 발생합니다. 반드시 if stack: 조건문으로 확인하는 습관을 들이세요.
2. pop(0) 금지: 리스트에서 pop(0)은 $O(N)$의 시간이 걸립니다. 스택은 무조건 뒤에서 넣고 빼는 append()와 pop()을 사용하세요.
3. 결과를 뒤집어야 할 때: 스택에 쌓인 순서의 역순이 결과라면 stack[::-1]이나 while stack: result.append(stack.pop())을 사용합니다.