BOJ 4889 - 안정적인 문자열

문제

백준 온라인 저지 - 4889번

풀이 과정

여는 괄호와 닫는 괄호를 적절히 변환하여 짝이 맞도록 하는 방법을 찾는 문제입니다.

괄호 짝 맞추기 문제와 유사한 컨셉으로 문제를 해결할 수 있습니다.

우선 여는 괄호({)의 경우 해당 괄호가 안정적인지는 이 괄호만 봐서는 알 수 없습니다. (이후에 나오는 괄호에 영향을 받음)

대신에 닫는 괄호(})의 경우 이전에 여는 괄호가 존재해야만 안정적인 문자열을 만들 수 있습니다.

만약 닫는 괄호가 나왔는데 여는 괄호가 존재하지 않을 경우 유일한 방법은 해당 괄효를 여는 괄호로 바꾸는 것 뿐입니다.

이룰 위해 스택 을 활용해서 괄호 종류에 따라 push, pop 을 수행하고 최종적으로 남는 여는 괄호의 개수 / 2 가 필요한 닫는 괄호의 개수입니다.

코드

import sys


def solution(string):
    change = 0
    stack = []

    for bracket in string:
        if bracket == '{':
            stack.append('{')
        else:
            if not stack:
                stack.append('{')
                change += 1
            elif stack[-1] == '{':
                stack.pop()

    change += len(stack) // 2

    return change


if __name__ == '__main__':
    question_number = 1

    while True:
        string = sys.stdin.readline().strip()
        if string[0] == '-':
            break

        answer = solution(string)
        print(f"{question_number}. {answer}")

        question_number += 1