[프로그래머스] 괄호 변환

문제

• 균형잡힌 괄호 문자열: '('와 ')'로만 이루어진 문자열이 있을 경우, '('의 개수와 ')'의 개수가 같은 경우
• 올바른 괄호 문자열: '('와 ')'의 괄호의 짝도 모두 맞을 경우

균형잡힌 괄호 문자열이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.

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

균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 return하도록 solution 함수를 완성해 주세요.

매개변수 설명

• p는 '('와 ')'로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
• 문자열p를 이루는 '('와 ')'의 개수는 항상 같습니다.
• 만약 p가 이미 '올바른 괄호 문자열'이라면 그대로 return 하면 됩니다.

풀이

구현문제

코드

def solution(p):
    answer = ''
    if checkRight(p):
        return p
    return solve(p)

def solve(w):
    if w == '': return ''
    index, num = 0, 0
    while True:
        num += 1 if w[index]=='(' else -1
        index += 1
        if num == 0:
            break
    u, v = w[:index],w[index:]
    if checkRight(u): # u가 올바른 괄호 문자열인 경우
        return u + str(solve(v))
    return '(' + str(solve(v)) + ')' + reverse(u)

def reverse(u):
    result = ''
    for i in range(1,len(u)-1):
        result += '(' if u[i] == ')' else ')'
    return result

def checkRight(sen):
    status = 0
    for s in sen:
        if s == '(': status += 1
        else: status -= 1
        if status < 0: return False
    return True