📝 분석

• 문자열의 길이를 2~1000자로 제한하고 있으므로, 시간복잡도를 크게 신경쓰지 않아도 된다.
  
• 올바른 문자열을 검사하는 로직과 균형잡힌 문자열을 검사하는 로직이 필요하다.
  • 균형잡힌 문자열을 검사한 뒤, 첫 글자가 '('이면 올바른 문자열이다.
• 문자열 검사 로직(문제에서 제시된 1~4단계)가 재귀적으로 돌아야하므로, solution 함수 자체를 재귀함수로 만든다. (이 부분 때문에 고민을 많이 했다. 보통 재귀문제들은 따로 재귀함수를 만들어서 구현하는 것이 대부분이니까...)

📌 코드

def isBalanced(p) :
    start = 0
    for i in range(len(p)):
        if p[i] == '(':
            start+=1
        elif p[i] == ')':
            start-=1
        if start == 0:
            return i


def solution(p) :
    answer = ''
    if p == '':
        return answer
    i = isBalanced(p)
    # seperate u, v
    u = p[:i+1] # i번째 인덱스의 글자까지 포함하기 때문에 i+1
    v = p[i+1:]

    if u[0] == '(':
        answer = u + solution(v)
    else:
        answer = '('
        answer += solution(v)
        answer += ')'
        nu = ''
        for i in range(1, len(u)-1):
            if u[i] == '(':
                nu += ')'
            else:
                nu += '('
        answer += nu
    
    return answer