[백준] 4889 - 안정적인 문자열

1. 문제

4889번: 안정적인 문자열

2. 개요

스택을 이용한 괄호문제.

사용할 수 있는 2개의 연산 ( ‘{’ 를 ‘}’ 로 바꾸기, ‘}’를 ‘{’로 바꾸기)를 이용해 완전한 괄호를 만들기 위한 최소 연산의 횟수를 구하면 된다.

3. 코드 및 추가내용

import sys

t = 0
while True:
    s = sys.stdin.readline().rstrip()

    if '-' in s:
        break

    stk = []
    ans = 0
    for char in s:
        if char == '{':
            stk.append(char)

        else:
            if stk and stk[-1] == '{':
                stk.pop()
            else:
                stk.append(char)

    for i in range(0, len(stk), 2):
        if stk[i] == stk[i+1]:
            ans += 1
        else:
            ans += 2

    t += 1 

    print("%d. %d" %(t, ans))

일단 스택을 이용해 완전한 괄호들을 모두 제거한 후,

두 자리씩 살펴보면서 같은 경우에는 1, 서로 다른 경우에는 2를 더해주면 된다.

같은 경우 ‘{{’, ‘}}’ 에는 하나만 바꿔주면 되고, 다른 경우는 ‘{}’의 경우 완전하기 때문에 이미 걸러져 나올 수 없고, ‘}{’의 경우엔 양쪽 모두 바꿔줘야 하기 때문.