[Baekjoon] 4889_안정적인 문자열

Silver I

문제(출처: https://www.acmicpc.net/problem/4889)

---

<안정적인 문자열>

문제 

 

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

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

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.
문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

 

 

입력

 

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

 

 

출력 

 

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

 

 

문제 풀이

- 초기 코드: 틀렸습니다

 

import sys

if __name__=='__main__':
    num=1

    while True:
        data=sys.stdin.readline().strip()
        if data.count('-')>0:
            break

        stack=[]
        cnt=0
        for i in data:
            if i=='{':
                stack.append(i)
            else:
                if len(stack)==0:
                    cnt+=1
                else:
                    stack.pop()

        if len(stack)%2==0:
            cnt+=len(stack)//2
        else:
            cnt+=len(stack)
        print(str(num)+'. '+str(cnt))
        num+=1

 

❓ 왜 틀렸는가?

예시에 있는 {{{}는 고려했지만 }}}{ 와 같은 경우를 고려하지 못했기 때문이다. 앞으로는 반례 찾는 생각도 많이 해야겠다 🤔

 

 

- my solution

import sys

if __name__=='__main__':
    num=1

    while True:
        data=sys.stdin.readline().strip()
        if data.count('-')>0: # 종료 조건
            break

        stack_left=[] # {
        stack_right=[] # }
        cnt=0
        for i in data:
            if i=='{':
                stack_left.append(i)
            else:
                if len(stack_left)==0:
                    stack_right.append(i)
                else: # 안정적
                    stack_left.pop()

        # 안정적으로 바꾸는데 필요한 최소 연산의 수
        if len(stack_left)!=0:
            cnt+=len(stack_left)//2+len(stack_left)%2
        if len(stack_right)!=0:
            cnt+=len(stack_right)//2+len(stack_right)%2

        print(str(num)+'. '+str(cnt))
        num+=1

 

• num : 출력문 사용
• 데이터 세트 입력
• 종료 조건 설정 : -가 존재하면 입력의 마지막
• stack_left : {
• stack_right: }
• '{' 라면 stack_left에 추가
• '}' - stack_left가 비었다면 stack_right에 추가 -> 괄호를 여는 괄호로 바꿔야 함
  - stack_left에 값이 있다면 stack_left를 pop
  
  
• 안정적으로 바꾸는데 필요한 최소 연산의 수 계산
  - stack_left와 stack_right의 개수를 구하여 각각 2로 나눈 몫과 나머지를 더해줌

 

❓ 왜 안정적으로 바꾸는데 필요한 최소 연산의 수를 저렇게 계산했는가?

만약 '}}{{'를 입력받아 stack_left에 {{ 이 있고 stack_right에 }}이 있다고 하자. 그렇다면 각각을 다 반대 괄호로 바꾸는 것이 아니라 하나씩만 바꿔 {}{}로 만들어 최소 연산의 수를 2로 구할 수 있다. 

이런 식으로 생각하여 각각의 stack에 2개씩 짝지을 수 있다면 하나만 바꿔 최소 연산으로 만들 수 있다고 생각하였다. 

 

만약 '}}}{{{' 라면 stack_left에 {{{ 이 있고 stack_right에 }}}이 있게 된다. 위의 해결 방법과 같이 stack_left의 2개 중 하나만 }로 바꿔 안정적으로 바꿀 수 있으며 stack_left에는 { 하나만 남게 된다. stack_right도 같이 하나만 {로 바꿔 안정적으로 바꾼 후 stack_right에는 } 하나만 남게 된다. {}}{{}로 각 stack에 하나씩 남으므로 각자 반대 괄호로 바꾸면 안정적인 문자열을 만들 수 있게 되는 것이다.

 

:)  stack_right와 stack_left의 개수를 센 후 2로 나눈 몫과 나머지를 더해주면 안정적인 문자열로 만드는데 최소 연산의 수를 구할 수 있다.

 

---

생각🤔

 

문제를 해결한 후 생각해보면 stack_left와 stack_right를 사용하지 않고 단순히 {와 }의 개수를 이용하여 간단하게 해결할 수 있었을 것 같다는 생각이 든다.

 

주어진 예제 말고도 반례를 생각해낼 수 있도록 노력-!

 

---