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

괄호 변환

문제 링크 programmers.co.kr/learn/courses/30/lessons/60058

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

---

문제 설명

카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.

  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.

  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.

  4-3. ')'를 다시 붙입니다.

  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.

  4-5. 생성된 문자열을 반환합니다.

 

코드

def balance(brackets):
    open_bracket, close_bracket = 0, 0
    for i, bracket in enumerate(brackets):
        if bracket == '(':
            open_bracket += 1
        elif bracket == ')':
            close_bracket += 1
        if i!= 0 and open_bracket == close_bracket:
            return (brackets[:i+1], brackets[i+1:])
    return ('', '')

def collect(brackets):
    stack = []
    for bracket in brackets:
        if bracket == '(':
            stack.append(stack)
        elif stack:
            stack.pop()
        else:
            return False
    return not stack

def reverse(brackets):
    answer = ''
    for bracket in brackets:
        if bracket == '(':
            answer += ')'
        elif bracket == ')':
            answer += '('
    return answer

def solution(brackets):
    if not brackets:
        return brackets
    u, v = balance(brackets)
    if collect(u):
        return u+solution(v)
    else:
        return '('+ solution(v) +')'+reverse(u[1:-1])
        
        

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

    if not brackets:
        return brackets

 

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

def balance(brackets):
    open_bracket, close_bracket = 0, 0
    for i, bracket in enumerate(brackets):
        if bracket == '(':
            open_bracket += 1
        elif bracket == ')':
            close_bracket += 1
        if i!= 0 and open_bracket == close_bracket:
            return (brackets[:i+1], brackets[i+1:])
    return ('', '')
    

    u, v = balance(brackets)

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.

  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

def collect(brackets):
    stack = []
    for bracket in brackets:
        if bracket == '(':
            stack.append(stack)
        elif stack:
            stack.pop()
        else:
            return False
    return not stack

    if collect(u):
        return u+solution(v)

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.

  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.

  4-3. ')'를 다시 붙입니다.

  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.

  4-5. 생성된 문자열을 반환합니다.

def reverse(brackets):
    answer = ''
    for bracket in brackets:
        if bracket == '(':
            answer += ')'
        elif bracket == ')':
            answer += '('
    return answer

        return '('+ solution(v) +')'+reverse(u[1:-1])