BOJ 4889번: 안정적인 문자열

www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

문제풀이:

스택을 이용한 괄호체크 문제와 똑같이 푼다.

"{"가 나올 경우에는 스택에 추가하고, "}"가 나올 경우에는 스택에서 하나를 pop 하는데, 이때 스택이 비어있는 경우 "}"->"{"로 바꾸는 연산을 수행해야 하므로 ans++ 후 스택에 "{"를 추가한다.

 

주어진 입력을 모두 체크한 후 스택이 비어있지 않은 경우 "{"를 "}"로 바꾸는 연산이 필요한데 한 번 연산하면 스택에서 두개 씩 pop한다.

 

import sys

num = 0
while (True):
    data = sys.stdin.readline().rstrip()
    if (data[0]=="-"):
        break
    num+=1
    ans = 0
    stack = []

    for i in data:
        if (i=="{"):
            stack.append(i)
        else:
            if (len(stack)==0):
                ans += 1 # "}" -> "{"
                stack.append("{")
            else:
                stack.pop()
    while (len(stack)>0):
        stack.pop()
        ans += 1 # "{" -> "}"
        stack.pop()
    
    print("%d. %d" % (num, ans))