[백준 4889] 안정적인 문자열(Python)

https://www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

}{

{}{}{}

{{{}

---

예제 출력 1

1. 2

2. 0

3. 1

풀이 설명

1. '{'를 저장할 stack을 만든다.

2. 입력받은 문자열을 탐색하면서

  2-1. stack이 비어있는데 '}'을 만나면 count를 1 올린다.

  2-2. stack이 비어있지 않고 '}'을 만나면 stack에서 하나를 지운다.

  2-3. '{'를 만나면 stack에 넣는다.

3. stack의 길이 / 2를 count에 더하고, answer 배열에 추가한다.

4. answer의 내용을 주어진 포맷에 맞게 출력한다.

Python3 코드

answer = []

while True:
    stack = []
    count = 0
    s = input()
    if '-' in s:
        break
    for i in range(len(s)):
        if not stack and s[i] == '}':
            count += 1
            stack.append('{')
        elif stack and s[i] == '}':
            stack.pop()
        else:
            stack.append(s[i])
    count += len(stack)//2
    answer.append(count)

for i in range(len(answer)):
    print(i+1, '. ', answer[i], sep='')