2022.02.28 [백준] (python 파이썬) 안정적인 문자열

 

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

4889번: 안정적인 문자열

 

---

풀이

이 문제는 스택을 이용해서 해결했다.

만약 여는 괄호가 나오면 stack에 저장하고,

닫는 괄호가 나오면 두가지 경우로 생각할 수 있다.

1. 만약 stack이 비어 있을 경우 괄호의 짝이 맞지 않기 때문에 여는 괄호로 바꾼 뒤 stack에 저장. 괄호를 바꿨기 때문에 cnt를 증가시킴.
2. 만약 stack의 마지막 인덱스 값이 여는 괄호이면 서로 짝이 맞기 때문에 이 괄호 쌍은 더 이상 비교할 필요가 없다. 그래서 stack.pop을 해서 여는 괄호를 지워준다.

문자열을 모두 확인한 뒤, 만약 stack에 데이터가 들어있으면 여는 괄호가 많아 짝이 맞지 않는 상황이다.

그런데 문제에서 문자열은 짝수의 조건을 주었기 때문에, stack에는 여는 괄호가 짝수개 있을 것이다.

그럼 이 배열의 반을 닫는 괄호로 바꾸면 모든 괄호가 짝이 맞을 것이다. 그러므로 cnt에 stack의 길이//2를 더해주면 해당 문자열을 모두 짝이 맞게 하기 위해 괄호를 바꾼 횟수가 나온다.

#테스트 케이스 카운팅
num=1
while True:
    s=input()
    if s[0]=='-':
        break
    # 여는 괄호를 담을 stack
    stack=[]
    # 괄호를 바꾼 횟수
    cnt=0
    for i in s:
        if i=='{':
            stack.append(i)
        elif i=='}':
            # 닫는 괄호가 나왔는데 stack이 비어있으면
            # 짝이 맞지 않기 때문에 여는 괄호로 바꾼 뒤,
            # stack에 저장, cnt증가
            if not stack:
                stack.append('{')
                cnt+=1
            # stack의 제일 뒤 인덱스 값이 여는 괄호면
            # 서로 짝이 맞으므로 여는 괄호 제거
            elif stack[-1]=='{':
                stack.pop()
    # 문자열을 모두 확인 했는데 stack에 데이터가 들어있으면
    # 여는 괄호가 많아서 stack에 여는 괄호가 들어있다는 의미
    # 문제에서 문자열은 짝수로 주어졌으므로 cnt에 stack의 길이//2를 더해줌
    if stack:
        cnt+=len(stack)//2
    print(num,'. ',cnt,sep='')
    num+=1