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

출처: [백준] 4889번 안정적인 문자열

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	2235	1068	890	46.793%

---

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

---

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 ‘-‘가 한 개 이상 주어진다.

---

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

---

예제 입력 1

}{
{}{}{}
{{{}
---

예제 출력 1

1. 2
2. 0
3. 1

---

출처

• ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2009 Arab Collegiate Programming Contest A번
  • 문제를 번역한 사람: baekjoon

---

알고리즘 분류

• 자료 구조
• 문자열
• 스택

---

소스코드

import math
import sys

input = sys.stdin.readline
i = 0
while True:
    i += 1
    input_string = list(input().rstrip())

    if input_string[0] == '-':
        break
    else:
        open_bracket = []
        close_bracket = []
        for x in input_string:
            if x == '{':
                open_bracket.append(x)
            elif x == '}':
                if open_bracket:
                    open_bracket.pop()
                else:
                    close_bracket.append(x)

        count = math.ceil(len(open_bracket) / 2) + math.ceil(len(close_bracket) / 2)
        print(f"{i}. {count}")