[Seop's의 코드풀이] 백준 4889 안정적인 문자열 - Python

이번에 풀어볼 문제는 백준 4889번 안정적인 문자열이라는 문제입니다.

문제는 다음과 같습니다.

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

4889번: 안정적인 문자열

 

 

알고리즘 문제를 몇번 풀어보신 분이라면 올바른 괄호를 구성하는 문제는 한번쯤을 풀어보셨을 것이라 생각이듭니다.

하지만 이 문제는 올바를 괄호를 체크하는 것 뿐만 아니라 바르게 만들어 주어야 합니다. 그리고 바르게 만들기 위해 괄호를 뒤집어야 하는

최소 횟수를 정답으로 요구합니다. 

 

문제해결 IDEA 

- 왼쪽 괄호('{') 를 저장하는 Stack을 맏듭니다.

- 오른쪽 괄호가 나왔을때 왼쪽 괄호 stack을 pop 합니다. stack이 비어있을 경우 Count를 1 더하고 왼쪽 괄호 Stack에 '{'를 적재합니다.

- 문자열을 끝까지 탐색한 후 왼쪽 괄호 Stack이 비어있지 않는다면 Stack의 길으를 2를 나눈 값을 Count에 더해주면 정답입니다.

 

 

전체적인 코드는 다음과 같습니다.

질문과 피드백은 언제나 감사드립니다.

import sys
input = sys.stdin.readline

def soluction(s) :
    left_stack = []
    cnt = 0
    for i in s :
        if i == "{" :
            left_stack.append(i)
        else :
            if left_stack :
                left_stack.pop()
            else :
                cnt += 1
                left_stack.append("{")
        if i == "-" :
            return -1
    
    if left_stack :
        cnt += len(left_stack)//2
    return cnt


if __name__ == "__main__":
    num = 1
    while True :
        string = input().rstrip()
        answer = soluction(string)
        if answer != -1 :
            result = str(num) + ". " + str(answer)
            print(result)
            num += 1
        else :
            break