[18번] 괄호 변환

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

코딩테스트 연습 - 괄호 변환

 

구현, 재귀 문제

 

# 균형잡힌 문자열의 인덱스
def balanced_index(p):
    cnt = 0
    for i in range(len(p)):
        if p[i] == '(':
            cnt += 1
        else:
            cnt -= 1
        if cnt == 0:
            return i + 1


# 올바른 문자열 여부
def is_proper(p):
    cnt = 0
    for ch in p:
        if ch == '(':
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            return False
    return True


def solution(p):
    rst = ""
    if p == '':
        return rst

    idx = balanced_index(p)
    u = p[:idx]
    v = p[idx:]

    if is_proper(u):
        return u + solution(v)
    else:
        rst += '('
        rst += solution(v)
        rst += ')'
        tmp = list(u[1:-1])
        for i in range(len(tmp)):
            if tmp[i] == '(':
                tmp[i] = ')'
            else:
                tmp[i] = '('
        rst += "".join(tmp)
        return rst


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