괄호 변환

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60058?language=python3

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

문제에서 문자열을 변환하는 방법에 대해 상세하게 설명하고 있으므로

착실하게 구현하면 해결할 수 있습니다.

 

문자열이 "올바른 문자열"이 아니라면 재귀적으로 변환하는 구조이므로

재귀 함수를 사용하여 구현했습니다.(recurvise 함수)

 

문자열 p가 "균형잡힌 문자열"로 주어지므로 일일이 문자열의 마지막까지 괄호의 수를 확인해줄 필요는 없습니다.

def divide(w:str) -> tuple:  # 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    cntOpen, cntClose = 0, 0
    for i in range(len(w)):
        ch = w[i]
        if ch == '(':
            cntOpen += 1
        else:
            cntClose += 1
        if cntOpen == cntClose:
            return (w[:i+1], w[i+1:])

def isProperString(s:str) -> bool:  # "균형잡힌 문자열"인 s가 "올바른 문자열"인지 확인
    cntOpen, cntClose = 0, 0
    for ch in s:
        if ch == '(':
            cntOpen += 1
        else:
            cntClose += 1
        if cntClose > cntOpen:
            return False
    return True

def convertBrackets(s:str) -> str:  # u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
    temp = ''
    for i in range(1, len(s)-1):
        if s[i] == '(':
            temp += ')'
        else:
            temp += '('
    return temp

def recursive(s:str) -> str:
    if s == '': # 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
        return ''
    u, v = divide(s)
    if isProperString(u):   # 3단계
        return u + recursive(v)
    else:   # 4단계
        return '(' + recursive(v) + ')' + convertBrackets(u)

def solution(p):
    answer = recursive(p)
    return answer