[백준/파이썬] 4889 안정적인 문자열 (자료 구조) - 스택, 덱 사용하기

➰ 4889번 안정적인 문자열

---

▪ 문제

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

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

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

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

▪ 입력

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

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

▪ 출력

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

 

💡 구현 아이디어

---

리스트로도 구현이 가능한데, 덱을 연습해보고자 모듈 collections의 클래스 deque을 사용했다. 관련 내용은 이곳에 정리했다. 

 

여기서 사용한 덱은 리스트로도 구현 가능한 append(), pop() 정도만 사용하긴 했다. 그래도 시간 복잡도 측면에서 덱이 훨씬 효율적이므로 덱의 사용법도 알고 있으면 좋다. 

 

이 문제 풀이는 크게 1)입력 받기, 2)문자열 덱에 저장하기, 3)연산 횟수 세기 세 가지로 나뉜다. 

 

1) 입력 받기

'---'와 같은 문자열이 입력 될 때까지 무한 루프로 입력을 받는 거라 while True문 안에 if-break문으로 반복문과 제어문을 작성했다.

 

while True:
    input_str = list(input().rstrip())
    if input_str[0] == '-':
        break

 

2) 불완전한 괄호쌍들만 덱에 저장하기

입력 받은 문자열 중 바로 앞 문자, 즉 다른 괄호와 쌍을 이룰 수 있으면 deque.pop() 함수를 사용해서 바로바로 삭제했다. 

 

예를 들어 바로 앞의 문자가 '{'이고 지금 입력 받은 문자가 '}'라면 지금 차례의 문자는 덱에 저장하지 않고, 바로 앞에서 저장한 문자는 삭제했다. 

 

여기까지 완료하면 str 덱에는 불완전한 괄호쌍들만 남게 된다.

 

	str = deque() # 불완전한 괄호쌍들만 남기기

    for i in range(len(input_str)):
        if input_str[i] == '{':
            str.append('{')
        else: # 문자가 '}' 라면
            if len(str) > 0 and str[-1] == '{':
                str.pop()
            else:
                str.append('}')

 

3) 연산 횟수 세기

항상 이런 알고리즘 문제 풀면 고등학교 때 수능 수학 공부했던 거랑 비슷하게 느끼는데, 풀이를 생각하는 사고 과정의 흐름이 아주 비슷하기 때문이다. 암튼 하고 싶었던 얘기는, 문제 풀이에서 몇 개의 예시를 관찰하고 그 관찰을 통해 발생할 수 있는 모든 경우들을 시행착오를 거치지 않고 빠른 시간 안에 생각해 내는 것이 중요하다. 

 

불완전한 괄호쌍들만 남은 덱 str에서 있을 수 있는 괄호쌍들의 경우는 총 세 가지이다.

{{ , }} , }{ 이렇게 세 가지로 나눌 수 있다.

 

좀 더 관찰을 해보면 앞의 두 개 {{ 와 }} 는 결국 최소 연산 횟수는 한 번이므로 하나로 묶을 수 있고,

}{ 는 연산 횟수가 2회이므로 아예 다른 경우로 분류해야 한다. 

 

	cnt = 0
    
    # str에서 연산 횟수 구하기
    if len(str) == 0:
        cnt = 0
    else:
        for i in range(0, len(str)-1, 2):
            # str에는 원소가 짝수 개만 남았을 것이고
            # {{, }}, }{ 세 가지 경우가 있을 것임
            if str[i] == str[i+1]:
                cnt += 1
            else:
                cnt += 2

 

전체 소스 코드는 다음과 같다.

 

💻 소스 코드

---

# 4889 두 번째 풀이
import sys
from collections import deque

input = sys.stdin.readline
ans = []

while True:
    input_str = list(input().rstrip())
    if input_str[0] == '-':
        break

    str = deque() # 불완전한 괄호쌍들만 남기기
    cnt = 0 # 연산 횟수

    for i in range(len(input_str)):
        if input_str[i] == '{':
            str.append('{')
        else: # 문자가 '}' 라면
            if len(str) > 0 and str[-1] == '{':
                str.pop()
            else:
                str.append('}')

    # str에서 연산 횟수 구하기
    if len(str) == 0:
        cnt = 0
    else:
        for i in range(0, len(str)-1, 2):
            # str에는 원소가 짝수 개만 남았을 것이고
            # {{, }}, }{ 세 가지 경우가 있을 것임
            if str[i] == str[i+1]:
                cnt += 1
            else:
                cnt += 2

    ans.append(cnt)

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