Stack 예시문제

 

기본 예제

# 스택을 구현해 봅시다.
# 구현한 스택을 이용하여 3개의 데이터를 스택에 저장하고 다시 3번꺼내서 출력해봅니다.

#간단한 스택
top = -1
stack = [0] * 10

top += 1 # push(1)
stack[top] = 1

top += 1 # push(2)
stack[top] = 2

top += 1 # push(3)
stack[top] = 3

top -= 1 #pop()
print(stack[top+1])
top -= 1 #pop()
print(stack[top+1])
top -= 1 #pop()
print(stack[top+1])

 

 

Stack의 활용 : 백준 9012번 괄호

 

https://www.acmicpc.net/problem/9012

import sys

def is_valid_parentheses(string):
    stack = []
    
    for char in string:
        if char == '(':
            stack.append(char)  # 여는 괄호는 스택에 추가
        else:
            if stack:  # 스택이 비어있지 않으면 pop
                stack.pop()
            else:  # 스택이 비어있는데 닫는 괄호가 나오면 잘못된 문자열
                return "NO"
    
    return "YES" if not stack else "NO"  # 스택이 비었으면 YES, 남아있으면 NO

# 입력 받기
n = int(sys.stdin.readline().strip())
for _ in range(n):
    print(is_valid_parentheses(sys.stdin.readline().strip()))

append 이용하는 방법

 

1. stack = [] : 괄호를 저장할 스택 선언
2. 문자열을 한 글자씩 검사:
   1. 여는 괄호 ( → 스택에 추가
   2. 닫는 괄호 ) → 스택에서 하나 제거
   3. 닫는 괄호가 먼저 나오거나, 비었는데 닫으려 하면 NO
3. 반복이 끝나고 스택이 비어 있으면 YES, 남아있으면 N

---

txt = input()

top = -1
stack = [0] * 100

ans = 'Yes' # 짝이 맞다고 가정

for x in txt:
    if x == '(': # 여는 괄호 push
        top += 1
        stack[top] = x
    elif x == ')':
        if top == -1: # 스택이 비어있으면
            ans = 'No'
            break # for x
        else:
            top -= 1 # 소괄호만 있으므로 비교 작업 생략

if top > -1: # 여는 괄호가 남아있으면
    ans = 'No'

print(ans)

 

top 을 이용하는 방법 (더 빠름)

 

1. 문자열 txt를 입력받은 뒤, 스택을 초기화(top = -1, 최대 100칸).
2. 문자 하나씩 확인:
   1. '('일 때: top을 증가시키고 '('를 스택에 저장.
   2. ')'일 때: 스택이 비어있으면(top == -1) 바로 'No'로 판단하고 반복 종료, 그렇지 않으면 top을 감소시키며 스택에서 '(' 제거.
3. 반복이 모두 끝난 뒤, 스택에 '('가 남아있으면 (top > -1이면) 'No'.
4. 최종적으로 'Yes' 혹은 'No'를 출력.