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

• 백준 4889: 안정적인 문자열 Silver I
• 문제링크

4889번: 안정적인 문자열

나의 접근

1. '{' 인 경우에는 stack에 추가해준다.
2. '}' 인 경우에는
   1. stack이 비어있을 경우, '{'로 바꾸어서 stack에 추가해준 후 count를 추가한다.
   2. stack이 비어있지 않을 경우, 가장 상위의 원소를 pop 해준다.
3. stack에 남아있는 원소들의 개수를 2로 나누어 주면 해당 스택이 안정적인 문자열이 되기 위해 필요한 작업의 최소 수를 알아낼 수 있다.
4. 최종적으로 len(stack) // 2 + count 해주면 된다.

tc = 0
while True:
    stack = []
    tc += 1
    s = list(input())
    if '-' in s:
        break

    count = 0

    for i in range(len(s)):
        if s[i] == '{':					#1
            stack.append(s[i])

        elif s[i] == '}':				
            if len(stack) == 0:			# 2.1
                stack.append('{')
                count += 1
            else:						# 2.2
                stack.pop()
    
    print('{}. {}'.format(tc, len(stack) // 2 + count))	# 3