[Python] 괄호변환

def solution(p):
    def divide_p(p) :
        count_l = 0
        count_r = 0
        for i in range(len(p)) :
            if p[i] == '(' :
                count_l += 1
            else :
                count_r += 1
            if count_l == count_r :
                break
        return p[:i+1], p[i+1:]
    
    def right(u) :
        result = True
        count = 0
        for i in u :
            if i == '(' :
                count += 1
            else :
                count -= 1
                
            if count < 0 :
                result = False
                break
        return result
    
    if p == '' :
        return ''
    
    u, v = divide_p(p)
    if right(u) == True :
        return u + solution(v)
    else :
        answer = '('
        answer += solution(v)
        answer += ')'
        
        temp_u = u[1:-1]
        for i in range(len(temp_u)) :
            if temp_u[i] == '(' :
                answer += ')'
            else :
                answer += '('
    return answer

---

풀이

재귀함수를 이용해서 풀어야한다. 또한 문제에서 주어진 올바른 괄호 문자열로 바꾸는 과정을 잘 참고해 코드를 짜야한다.

올바른 괄호 문자열로 바꾸는 과정

 

1) u, v를 분리해주는 함수 만들기

   def divide_p(p) :
        count_l = 0
        count_r = 0
        for i in range(len(p)) :
            if p[i] == '(' :
                count_l += 1
            else :
                count_r += 1
            if count_l == count_r :
                break
        return p[:i+1], p[i+1:]

< 올바른 괄호 문자열로 바꾸는 과정의 2번 >

왼쪽 괄호( " ( " )를 뜻하는 count_l과 오른쪽 괄호( " ) " )를 뜻하는 count_r, 두 변수를 설정하고

두 변수의 수가 같아지면 "균형잡힌 괄호 문자열"이 되므로 for문을 중단하고 i를 기준으로 u, v로 나눈다. 

 

2) u가 올바른 문자열인지 판별하는 함수

  def right(u) :
        result = True
        count = 0
        for i in u :
            if i == '(' :
                count += 1
            else :
                count -= 1
                
            if count < 0 :
                result = False
                break
        return result

< 올바른 괄호 문자열로 바꾸는 과정의 3번 >

u가 올바른 괄호 문자열이 되기 위해서는 '(' 의 역할이 중요하다.

왜냐하면 괄호의 시작은 '('가 되어야하고, 괄호가 왼쪽인지 오른쪽인지 count하는 과정에서 '('의 수가 컸으면 더 컸지 ')'의 수가 더 큰 경우라면 올바른 괄호 문자열이 아니다. ( 예를 들어 '())(())' 인 경우 )

 

따라서 for문을 통해 괄호를 하나씩 받아 '(' 인 경우에는 +1, ')'인 경우는 -1를 해준다.

count가 0보다 작아진다면 u는 올바른 괄호 문자열이 아니므로 result를 False로 바꾸고 중단한다.

 

3) p가 빈 문자열일 경우

   if p == '' :
        return '' 

< 올바른 괄호 문자열로 바꾸는 과정의 1번 >

 

4) u가 올바른 문자열일 경우, 아닐 경우

    u, v = divide_p(p)
    
    if right(u) == True :
        return u + solution(v) # 3-1
        
    else :
        answer = '(' # 4-1
        answer += solution(v) # 4-2
        answer += ')' # 4-3
        
        # 4-4
        temp_u = u[1:-1]
        for i in range(len(temp_u)) :
            if temp_u[i] == '(' :
                answer += ')'
            else :
                answer += '('
                
    return answer # 4-5

위의 1)에서 p를 슬라이스한 값을 u, v에 각각 저장한다.

 

< 올바른 괄호 문자열로 바꾸는 과정의 3-1번 >

위의 2)에서 right(u)의 함수의 결과가 True일 경우 (u가 올바른 문자열일 경우)

 u 와 solution(v)를 붙여 반환한다. (v는 solution( ) 함수를 다시 거치게 된다.)

 

< 올바른 괄호 문자열로 바꾸는 과정의 4번 >

right(u)의 함수 결과가 False일 경우 (u가 올바른 문자열이 아닐 경우)  

예) u = '))((',  v = '()'

① 4-1 ~ 4-3) answer = '(())', u=')('

② 4-4) answer = '(())()'

해당 과정을 따라 올바른 괄호 문자열로 바뀌게 된다.

 

 

 

참고한 풀이

https://www.youtube.com/watch?v=P605nU1g7wM&t=742s