1. 문제 설명

안정적인 문자열

2. 문제 분석

스택을 통해 {의 개수와 }의 개수를 맞춰가면서 카운트하자. 앞에 {에 담겨져 있다면 }가 들어올 때 안정적인 문자열이 되지만, 그렇지 않다면 바꿔주어야 한다.

3. 나의 풀이

import sys

idx = 1
while True:
    string = sys.stdin.readline().rstrip()
    if string[0] == '-': break
    stack = []
    cnt = 0

    for s in string:
        if s == '{':
            stack.append(s)
            # {는 스택에 저장
        elif s == '}' and stack:
            stack.pop(-1)
            # }가 들어왔을 때 앞에 {가 있었다면 안정적임
        elif s == '}' and not stack:
            cnt += 1
            stack.append('{')
            # }가 들어왔을 때 스택에 {가 없다면 }를 {로 변경한다.
    cnt += len(stack) // 2
    # 스택에는 [{{{{...]만 기록되어 있다. 안정적인 문자열로 바꾸려면 이 중 절반을 }로 변경해야 한다.
    print(f"{idx}. {cnt}")
    idx += 1