책 리뷰/파이썬 알고리즘 인터뷰

9장 스택,큐(1) - 스택이란? (예제-유효한 괄호)

조조링 2024. 11. 18. 23:45
728x90
반응형

스택(Stack)과 연결 리스트를 활용한 ADT 구현 및 유효한 괄호 문제 풀이

스택(Stack)은 LIFO(Last In, First Out) 구조를 가지는 대표적인 자료구조이다.

이는 가장 나중에 들어간 데이터가 가장 먼저 나오는 구조로, 다음 두 가지 주요 연산을 지원한다.

  • push(item): 스택의 맨 위에 데이터를 추가하는 연산
  • pop(): 스택의 맨 위 데이터를 제거하고 반환하는 연산

 

1. 연결 리스트를 활용한 스택 ADT 구현

스택은 배열 또는 연결 리스트를 이용하여 구현할 수 있다. 여기서는 연결 리스트를 활용한 스택 구현 방식을 살펴보려고 한다. 

 

연결 리스트 기반 스택 구현 코드

# 연결 리스트의 노드를 나타내는 클래스
class Node:
    def __init__(self, item, next):
        self.item = item  # 현재 노드의 값
        self.next = next  # 다음 노드를 가리키는 포인터

# 스택 ADT를 구현하는 클래스
class Stack: 
    def __init__(self):
        self.last = None  # 스택의 맨 마지막 노드를 가리키는 포인터
        
    def push(self, item):
        # 새 노드를 생성하여 현재 노드를 next로 연결
        self.last = Node(item, self.last)
        
    def pop(self):
        # 현재 노드의 값을 반환하고 포인터를 이전 노드로 이동
        if not self.last:
            raise IndexError("pop from empty stack")  # 스택이 비어있을 경우 예외 처리
        item = self.last.item
        self.last = self.last.next
        return item

 

코드 동작 원리

  1. Node 클래스:
    • 각 노드는 데이터를 저장할 item과 다음 노드를 가리키는 next 포인터를 가진다.
    • next를 활용하여 연결 리스트 형태로 노드를 연결한다.
  2. Stack 클래스:
    • last 포인터는 스택의 가장 위에 있는 노드를 가리킨다.
    • push 연산: 새 노드를 생성하여 last 포인터를 업데이트한다.
    • pop 연산: 현재 노드의 값을 반환한 뒤, last 포인터를 이전 노드로 이동시킨다.
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)

for _ in range(5):
    print(stack.pop())
    
    
# 5
# 4
# 3
# 2
# 1

 

스택 변수 stack의 입력된 값을 도식화하면 아래와 같다. 

  • stack은 각각 이전 값을 가리키는 연결 리스트로 구현되어 있으며, 가장 마지막 값은 last 포인터가 가리킨다. 

 

문제1. 유효한 괄호

괄호로 이루어진 문자열이 올바른지 확인하는 문제이다. 올바른 괄호란 모든 열리는 괄호가 닫히는 괄호와 짝이 맞아야하며,
짝의 순서도 일치해야 한다.
입력: ()[]{}   /  출력: True(모든 괄호가 열림과 닫힘이 짝을 이루며, 순서도 맞음)
입력: ([)]     / 출력: False(열림과 닫힘의 순서가 맞지 않음)
def isValid(s: str) -> bool:
    stack = []  # 스택 역할을 하는 리스트
    table = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    
    for char in s:
        # 닫는 괄호가 아니면 스택에 추가
        if char not in table:
            stack.append(char)
        # 닫는 괄호인 경우: 스택이 비어있거나 짝이 맞지 않으면 False
        elif not stack or table[char] != stack.pop():
            return False
        
    # 모든 괄호를 처리한 뒤 스택이 비어있으면 유효한 괄호
    return len(stack) == 0

 

코드 동작 원리

  1. 스택을 이용한 괄호 처리:
    • 열린 괄호는 stack에 추가한다.
    • 닫힌 괄호를 만날 경우, 스택의 최상단 값을 확인하여 짝이 맞는지 확인한다.
  2. 검사 과정:
    • 닫는 괄호와 열린 괄호가 짝이 맞지 않거나, 스택이 비어있으면 False를 반환한다.
    • 모든 문자를 확인한 뒤 스택이 비어있다면 True를 반환한다.

예제 실행

print(isValid("()[]{}"))  # True
print(isValid("([)]"))    # False
print(isValid("{[]}"))    # True

 

3. 코드 설명 및 도식화

스택의 변화 과정을 도식화:

 

입력 문자열: ({[]})

  1. ( 추가 → stack = ['(']
  2. { 추가 → stack = ['(', '{']
  3. [ 추가 → stack = ['(', '{', '[']
  4. ] 닫음 → stack = ['(', '{']
  5. } 닫음 → stack = ['(']
  6. ) 닫음 → stack = []

최종적으로 스택이 비어있으므로 유효한 괄호이다.

728x90
반응형