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

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

프로그래머스

 

 

 

def solution(p):
    answer = ""
    if len(p) == 0:
        return p
    if isCorrect(p):
        return p
    # 균형잡힌 괄호 u와 나머지 v로 분리
    left = 0
    right = 0
    for i in range(len(p)):
        if p[i] == '(': left += 1
        if p[i] == ')': right += 1
        if left == right:
            u = p[0:i+1]
            v = p[i+1:]
            break
    # 문자열 u가 올바른 괄호 문자열인지
    if isCorrect(u):
        # 맞으면 v에 대해 1단계부터 다시 수행하고 u에 이어 붙인다
        answer = u + solution(v)
    else:
        # 아니라면 ( + v에 대해 1단계부터 재귀 + ) + u의 첫번째 마지막 문제 제거하고 괄호 방향 뒤집기
        answer = "(" + solution(v) + ")" + make_new_u(u)
    
    return answer

def make_new_u(u):
    str = u[1:-1]
    new_u = ""
    for i in range(len(str)):
        if str[i] == '(' : new_u += ')'
        else: new_u += '('
    return new_u

def isCorrect(p):
    left = 0
    right = 0
    for i in range(len(p)):
        if p[i] == '(': left += 1
        if p[i] == ')' : right += 1
        if left < right: return False
    return True

 

 

문제 설명에 나온 알고리즘 그대로 코드로 구현하면 되는 문제

중복되는 계산만 함수로 따로 빼줬다. 

- 이 문자열이 올바른 문자열인지 확인하는 함수

- u의 첫번째 문자와 마지막 문자를 빼고, 나머지의 괄호 방향을 뒤집어서 반환하는 함수