2020 카카오 블라인드

괄호변환

🔗 전체 문제 : 괄호변환

'(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
'('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 균형잡힌 괄호 문자열 u, v로 분리합니다.
   단, u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 올바른 괄호 문자열 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 올바른 괄호 문자열이 아니라면 아래 과정을 수행합니다.
   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
   4-3. ')'를 다시 붙입니다.
   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
   4-5. 생성된 문자열을 반환합니다.

Python 코드

# 주어진 로직을 그대로 구현할 수 있는지 파악
# 재귀함수를 이해하고 작성할 수 있는지 파악
# 재귀함수 -> base case를 작성해야 한다.

def solution(p):
    # 입력이 빈 문자열인 경우, 빈 문자열을 반환
    if p == "":
        return p

    # 문자열을 u, v로 분리
    cnt, idx = 0, 0
    for i in range(len(p)):
        if p[i] == '(':
            cnt += 1
        else:
            cnt -= 1

        if cnt == 0:
            idx = i
            break

    u, v = p[:idx+1], p[idx+1:]

    # u가 올바른 괄호 문자열이라면 v에 대해 1단계부터 다시 수행
    if u[0] == "(": # 이미 잘린 데이터인 상태에서 시작하는 부위가 여는 괄호면 올바른거임!
        return u + solution(v)

    # 4번 과정
    else:
        # 4-4 과정
        new_u = ""
        for i in u[1:-1]:
            if i == "(":
                new_u += ")"
            else:
                new_u += "("

        return "(" + solution(v) + ")" + new_u

# test
print(solution("()))((()"))