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

1. 문제 출처

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

4889번: 안정적인 문자열

2. 풀이

"{"이 먼저 나와야  "}"과 짝을 지을 수  있기 때문에 "{"을 스텍에 집어 넣고 "}"이 나올 때마다 하나씩 꺼내었고,

스텍이 비었을 때 "}"가 나오면 "}"을 "{"으로 바꾸어야 하기 때문에 count를 1을 더해주고 스텍에 값을 "{" 을 추가하였다.

만약 "{" 이 더 많아서 stack이 남는 다면 그 중 절반은 "}"이 되어야 하므로 count +  int(len(stack)/2)를 출력한다.

 

 

 

def safe(s):
	# 횟수
    count = 0
    # 만약 빈 문자열이면 0을 반환
    if len(s) ==0:
        return 0
    # 스텍
    stack = []
    for idx in range(len(s)):
    # 만약 { 가 나온다면
        if s[idx] == "{":
        # 스텍에 추가
            stack.append(s[idx])
       # }가 나온다면
        else:
        	# 스텍이 비어있지 않으면 {을 하나 뺀다.
            if len(stack):
                stack.pop()
            else:
            # 비어있다면 } -> { 로 바꾸어 주고 스텍에 추가한다.
                stack.append("{")
                count +=1
        # 스텍이 남아 있다면 }만 남았으므로 짝을 맞추려면 절반은 변환해야 하므로 
        # + int(len(stack)/2)를 해준다.(나머지는 위에서 전부 짝을 맞추었다.)
    return count + int(len(stack)/2)

def solution():
    string = input()
    str_list = [] 
    while "-" not in string:
        str_list.append(string)
        string = input()
    for idx in range(len(str_list)):
        print(f"{idx+1}. {safe(str_list[idx])}")
        
solution()