[프로그래머스/파이썬] 괄호 변환(60058) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 괄호 변환(60058)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

균형잡힌 괄호 문자열 p를 문제에서 제시한 재귀 규칙에 따라 올바른 괄호 문자열로 변환하는 문제입니다.

코드

def solution(p):
    return recursion(p)

conv = {'(':')', ')':'('}
def recursion(p):
    if p == "": return p

    for i in range(2, len(p)+1):
        if not isBalanced(p[:i]): continue
        
        u, v = p[:i], p[i:]
        
        if isCorrect(u): return u + recursion(v)
        
        tmp = "(" + recursion(v) + ")"
        for c in u[1:-1]: tmp += conv[c]
        return tmp
    
def isCorrect(p):
    cnt = 0
    for c in p:
        if c=='(': cnt += 1
        elif cnt < 1: return False
        else: cnt -= 1
    return True

def isBalanced(p):
    return p.count("(") * 2 == len(p)


print(solution("(()())()"))

설명

재귀 함수에서 문자열 p를 가장 앞의 균형잡힌 문자열 u와 나머지 v로 분리합니다.

• u가 올바른 문자열이면 u + recursion(v)
• 아니면 "(" + recursion(v) + ")" + (u의 양끝 제거 후 괄호 뒤집기)

를 적용합니다.

균형 여부(isBalanced)와 올바름(isCorrect)을 분리해서 규칙을 그대로 구현한 풀이입니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---