greentea31's Note

https://programmers.co.kr/learn/courses/30/lessons/60058

풀이 과정

균형 잡힌 괄호 문자열을 줄 테니 올바른 괄호 문자열로 변환한 결과를 출력하라는 문제다.

균형잡힌균형 잡힌 괄호 문자열의 정의, 올바른 괄호 문자열의 정의, 균형 잡힌 괄호 문자열을 올바른 괄호 문자열로 바꾸는 방법을 전부 다 문제 지문에서 주었고, 문제가 시키는 대로 구현을 하면 된다.

1. 균형 잡힌 괄호 문자열 분리 방법

문자열의 앞에서 부터 (의 개수, )의 개수를 세면서 서로 같아지는 순간의 index까지 분리해 u, 그 이후는 v로 분리하면 된다 개수가 0, 0일 때 분리되지 않도록 주의해야 한다.

2. 올바른 괄호 문자열 판별법

스택을 써도 되지만 그냥 0으로 초기화된 정수 변수로도 판별할 수 있다. 

(을 인식하면 integer += 1

)을 인식하면 integer -= 1

문자열을 읽으면서 위와 같은 연산을 계속 해준다. 문자열을 읽는 도중에 integer가 중간에 0 이하로 떨어진다면, 괄호의 쌍이 맞지 않으므로 올바른 괄호 문자열이 아니라고 판단해주고, 문자열을 다 읽었는데 integer가 0이 아니라면 또 괄호의 쌍이 맞지 않으므로 올바른 괄호 문자열이 아니라고 판단해주면 된다. 다 읽었는데 integer가 0이면 올바른 괄호 문자열이라고 판단해주자.

ex) (()))( -> +1 +1 -1 -1 -1, 5번째 문자를 읽으면 -1이 됨

      (())( -> +1 +1 -1 -1 +1, 다 읽었는데 integer가 1임, 마지막 (에 대응되는 )이 없으므로 올바른 괄호 문자열이 아님

      (())() -> +1 +1 -1 -1 +1 -1, 문자열을 읽는 도중 정수가 음수로 떨어지지 않고, 다 읽으면 정수가 0으로 끝남, 올바른 괄호 문자열임

위의 2개만 알고 있으면 그냥 나머지는 문제에서 주어진대로 하면 된다.

소스 코드

def recursive_string(string):
    if string == '':
        return ''
    
    a, b = 0, 0
    for index in range(len(string)):
        if string[index] == '(':
            a += 1
        else:
            b += 1
        if a == b:
            u, v = string[:index+1], string[index+1:]
            break
    
    if right_string(u):
        return u + recursive_string(v)
    else:
        temp = '('
        temp += recursive_string(v)
        temp += ')'
        u = u[1:-1]
        for letter in u:
            if letter == '(':
                temp += ')'
            else:
                temp += '('
        return temp
        


def right_string(string):
    count = 0
    for letter in string:
        if letter == '(':
            count += 1
        else:
            count -= 1
        if count < 0:
            return False
    
    if count == 0:
        return True
    else:
        return False


def solution(p):
    return recursive_string(p)