Level 2. 괄호 변환

괄호 변환

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 괄호 변환

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

문제 설명

소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발

# 용어의 정의

'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 '균형잡힌 괄호 문자열'이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 '올바른 괄호 문자열'이라고 부릅니다.

'(' 와 ')' 로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열" 이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.

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. 생성된 문자열을 반환합니다.

"균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.

### 매개변수 설명

p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.

문제 풀이

# 문자열 p를 u,v로 분리
def div(p):
    p1,p2 = '',''
    for i in range(2,len(p)+1,2):
        if p[:i].count('(') == p[:i].count(')'):
            return p[:i], p[i:]

# 문자열 u가 올바른 괄호 문자열인지 확인
def bal(u):
    stack = []
    for i in u:
        if i == '(':
            stack.append(i)
        else:
            if not stack:
                return False
            stack.pop()
    return True

def solution(p):
    answer = ''
    #01
    if p == '':
        return ''
    #02
    u,v = div(p)
    #03
    if bal(u):
        return u + solution(v)
    #04
    else:
        answer += '(' #04-1
        answer += solution(v) #04-2
        answer += ')' #04-3

        for i in u[1:len(u)-1]: #04-4
            if i == '(':
                answer += ')'
            else:
                answer += '('
        return answer

# Code test
p = '(()())()'
solution(p)

....