[BOJ] 4889: 안정적인 문자열 solution

문제 소개

 

2020.02.24 기준,  실버 1티어 문제입니다.

문제 분류는 기존에 주어져 있지 않았고, 제가 stack과 string으로 부여했습니다.

 

어떻게 보면 간단하면서 어떻게 보면 되게 이해가지 않을 수도 있는 풀이입니다.

 

먼저, 문제를 풀 수 있는 아이디어부터 설명하고

코드를 설명하겠습니다.

 

 

문제 링크

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

4889번: 안정적인 문자열

아이디어

이 문제를 대충 읽고 풀으려 했을 때, 안정적인 문자열을 만들기 위해 문자를 추가하는 횟수를 구하는 문제로 착각할 수 있습니다. 하지만 문제에 "문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다." 라고 명시되어있습니다.

 

여기서 해볼 접근은

아! 그럼 문자열에 연산을 적용해야 하는 경우를 생각해보자!

일 것입니다.

 

문자열에 연산을 적용해야 하는 경우는 다음과 같습니다.

 

1. 앞에 여는 괄호가 없는데 닫는 괄호가 온 경우 ex. }{

2. 여는 괄호가 남았는데 문자열이 끝난 경우 ex. {{{}

 

이제 경우를 한가지씩 해결해봅시다.

첫번째의 경우는 앞에 여는 괄호가 없는데 닫는 괄호가 온 것입니다. 따라서 이 경우를 바로잡으려면 주어진 닫힌 괄호를 여는 괄호로 수정하고 뒤에 오는 닫는 괄호와 짝을 맺는 것입니다. 따라서 연산이 1회 증가하겠군요.

 

두번째의 경우는 여는 괄호는 남아있는데 문자열이 끝났을 때입니다. 근데, 여기서 우리는 문제에 주어진 조건 한가지를 생각해보면 쉽습니다. "문자열의 길이는 항상 길이는 짝수이다." 라는 조건 말이죠. 이 조건이 의미하는 바는 어떻게든 이 괄호 문자열이 성립할 수 있다는 것입니다. 따라서 1번 경우를 해결하면서 왔을 때, 무조건 남아있는 여는 괄호의 개수는 짝수입니다. 그리고 간단히 남은 여는 괄호의 개수 절반을 연산 횟수에 더해주면 이 문제를 해결 할 수 있습니다.

 

코드

case = 1
while True:
    # cnt: 현재까지 여는 괄호의 개수를 저장하는 변수
    cnt = 0
    # ans: answer
    ans = 0
    s = input()
    # 문제에 주어진 break 조건
    if s[0]=="-":
        break
    for i in s:
        # 여는 괄호가 주어진 경우
        if i == '{':
            cnt+=1
        # 닫는 괄호가 주어진 경우
        else:
            # 여는 괄호가 이전에 없는 경우
            if cnt <= 0:
                ans+=1
                cnt+=1
            # 여는 괄호가 이전에 있는 경우
            else:
                cnt-=1
    ans += cnt//2
    print("{}. {}".format(case,ans))
    case +=1

 

위에 설명한 아이디어를 코드로만 옮긴 것입니다.

추가로 설명할 게 없을 것 같습니다.

Rmx