괄호 변환 - 프로그래머스 lv.2

문제 링크

프로그래머스

풀이

# 올바른 괄호 문자열 확인
def is_correct(p: str) -> bool:
    stack = []
    # 여는 괄호와 닫는 괄호 개수 일치, 열린 후 닫히면 올바름
    for bracket in p:
        if bracket == '(':
            stack.append(bracket)
        elif stack:
            stack.pop()
        else:
            return False
    return not stack

# 균형잡힌 괄호 문자열로 분리
def split_brackets(p: str) -> tuple:
    open_count, close_count = 0, 0
    for i, bracket in enumerate(p):
        if bracket == '(':
            open_count += 1
        else:
            close_count += 1
        # 여는 괄호와 닫는 괄호 개수 동일한 지점에서 분리
        if open_count == close_count:
            return p[:i+1], p[i+1:]

# 괄호 뒤집기
def reverse_brackets(p: str) -> str:
    return ''.join([')' if bracket == '(' else '(' for bracket in p])

# 재귀적 변환, 균형잡힌 괄호 문자열로
def convert_brackets(p: str) -> str:
    # 빈 문자열이면 그대로 반환
    if not p:
        return p
    
    # 문자열을 균형잡인 괄호 문자열로 분리
    u, v = split_brackets(p)
    
    # 첫 번째가 올바른 괄호 문자열이면 두 번째 문자열 재귀적 변환
    if is_correct(u):
        return u + convert_brackets(v)
    # 올바르지 않으면 열고, v 재귀적 변환, 닫고, u 괄호 뒤집고 양끝 제거
    else:
        return '(' + convert_brackets(v) + ')' + reverse_brackets(u[1:-1])

# 올바른 괄호 문자열로 변환하여 반환
def solution(p: str) -> str:
    if is_correct(p):
        return p
    return convert_brackets(p)


if __name__ == "__main__":
    print(solution(p))