🚶‍♂️Road to 코테(7) - 스택 활용

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬

[추가] 좌충우돌, 파이썬으로 자료구조 구현하기

스택의 활용 : 수식의 괄호 쌍

주어진 괄호 문자열이 올바른지 판단하는 문제이다.
짝이 다 맞으면 맞는거 아닌가?

• 방법1 : 짝 맞추기해서 지워나가기. 물론, (())()()과 같은 경우만 동작한다.
  괄호가 여러 종류일 때는 그 방법으로만 해결이 되지 않는다. ({)}와 같은 경우 해결 불가.
• 방법2 : 붙어있는 ()과 {} 등을 지우는 방법도 있다.
  배열로 구현시 O(n^2)이 걸리고 연결리스트는 O(n)이다. 스택을 이용시 훨씬 간단해 진다.
  -> 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애는 것이라고 봐도 된다. ({(){}})을 살펴보자.

({(){}})을 앞에서 부터 읽어나가면 ({( 이후 )가 들어왔을 때 가장 최근에 들어온 여는 괄호를 없애서 ({가 된다. ({{}가 됐을 때도 다시 ({가 된다. 이후에 닫는 괄호가 들어오면 나머지 ({가 없어진다.
정리하자면,
1. 여는 괄호가 나오면 스택에 추가
2. 닫는 괄호가 나오면
2-1. 스택이 비어있으면 올바르지 않은 괄호 쌍
2-2. 스택의 top이 짝이 맞지 않으면 올바르지 않음.
2-3. 스택의 top이 짝이 맞는 괄호일 경우 pop
3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍.

연습문제 백준 4949번 균형잡힌 세상

import sys


while True:
  answer=True
  stack=[]
  sent=sys.stdin.readline().rstrip()
  if sent=='.':
    break
  for i in sent:
    if i=='(' or i=='[':
      stack.append(i)
      
    elif i==']':
      if len(stack) ==0:
        answer=False
        break
      else:
        gual=stack[-1]
      if len(stack) ==0 or gual != '[':
        answer=False
        break
      stack.pop()
      
      
    elif i==')':
      if len(stack) ==0:
        answer=False
        break
      else:
        gual=stack[-1]
      if len(stack) ==0 or gual != '(':
        answer=False
        break
      stack.pop()
  
  if len(stack) == 0  and answer:
    print('yes')
  else:
    print('no')
    
    

수 많은 예외처리를 뚫어야한다는것이 힘들었다.