백준 4889 안정적인 문자열 / python

문제 : 4889

풀이 point

stack을 활용하여 top과 현재 괄호가 { or } 인지 따라 횟수를 카운트 해준다.
괄호가 짝이 지어지지 않으면 바꿔주는 횟수가 늘어난다.

이를테면

풀이 코드

from collections import deque

idx = 0
while True:
  idx += 1
  string = input()
  if '-' in string:
    break

  cnt = 0
  Q = deque()
  for ch in string:
    if ch == '}' and Q:
      if Q[len(Q)-1] == '{':
        Q.pop()
    elif ch == '{':
      Q.append('{')
    else:
      cnt += 1
      Q.append('{')
  
  cnt += len(Q)//2
  print(f"{idx}.", cnt)