[Recursive - 재귀적 해결법] 괄호 변환 - Python

 

 

이번 문제는 괄호 변환입니다.

 

간단한 재귀적 함수를 구현하는 함수로서 문제를 잘 이해하는 것이 가장 중요한 부분이었습니다

 

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

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

 

주의 - 문제의 조건을 읽어보시고 아래를 읽어주세요

 

 

첫번째 조건을 체크하기 위해서는 단순한 코드면 충분합니다

 

#1번 체크
    if(p == ''):
        return p

 

2번째도 마찬가지로 간단합니다

단 이때 전체 조건중 재귀적으로 풀어야 한다는 부분이 있기 때문에 

함수를 분리하는것이 좋습니다.

 

def split(p):    
    u = ''
    v = ''
    count = 0
    
    for i in range(0, len(p)):
        
        if p[i] == '(':
            count += 1
        else:
            count -= 1
        
        if count == 0:
            u = p[ : i+1]
            v = p[i+1 : ]
            break
            
    
    return u, v

 

원리는 간단합니다 

 

멀쩡한 괄호 문자열임을 확인하기 위해서 count 변수를 사용하여

 ( 를 확인할 경우 + 1

 ) 를 확인할 경우 - 1 

 

count가 0이 되는 순간 (()) 식으로 닫힌 문자열이기 때문에 이를 기준으로 문자열을 잘라서 u ,v를 반환하면 됩니다

 

 

 

그후 올바른 괄호 문자열임을 확인하기 위하여 같은 방식으로 u를 검증하는 함수를 분리하여 생성합니다.

 

def checkBalanced(p):
    
    check = 0
    
    for i in p:
        
        if(i == '('):
            check += 1
        else:
            check -= 1
            
            if check < 0:
                return False
    
    return True
    
    

 

위 두 함수를 이용하여 3-1 조건에서 끝나는 함수들을 먼저 제거해 보면

 

다음 코드와 같습니다

 

def solution(p):
    answer = ''
    
    
    #1번 체크
    if(p == ''):
        return p
    
    u, v = split(p)
    
    if(checkBalanced(u)):
        v = solution(v)
        return u + v

 

이 때 가장 중요한 점은 solution 함수 자체를 재귀적으로 사용하는 것입니다.

 

4-2 에서만 재귀적이라는 표현을 사용하여 헷갈리시는 분들도 있겠지만

 

solution 함수를 다시 사용하는 것이 가장 중요한 부분입니다!

 

4단계 부터 이어서 진행한다면

 

#4번 체크
    w = ''
    
    #4-1
    w += '('
    
    #4-2
    w += solution(v)
    
    #4-3
    w += ')'
    
    #4-4
    u = u[1:-1]
    reverseU = []
    
    for i in u:
        if i == '(':
            w += ')'
        else:
            w += '('
            
    
    #4-5
    answer = w

 

 

빈 문자열을 준비한다음

 

가장 중요한 4-4를 살펴보도록 하겠습니다.

 

말 그대로 문자열을 뒤집는다는것에서 대부분 reverse 함수를 사용하시는 것을 생각하실텐데

 

"괄호 방향을 뒤집어서" 라고 표현했기 때문에 절대 문자열 전체를 뒤집으시면 안됩니다.

 

"(" => ")" 로 바꾸고 ")"=> "("

로 변환하며 첫 빈 문자열 w 에 붙여주시면 문제는 해결됩니다.

 

 

 

전체 코드는 다음과 같습니다.

 

최종 코드

def split(p):
    
    u = ''
    v = ''
    count = 0
    
    for i in range(0, len(p)):
        
        if p[i] == '(':
            count += 1
        else:
            count -= 1
        
        if count == 0:
            u = p[ : i+1]
            v = p[i+1 : ]
            break
            
    
    return u, v

def checkBalanced(p):
    
    check = 0
    
    for i in p:
        
        if(i == '('):
            check += 1
        else:
            check -= 1
            
            if check < 0:
                return False
    
    return True
    
    

def solution(p):
    answer = ''
    
    
    #1번 체크
    if(p == ''):
        return p
    
    u, v = split(p)
    
    if(checkBalanced(u)):
        v = solution(v)
        return u + v
    
    #4번 체크
    w = ''
    
    #4-1
    w += '('
    
    #4-2
    w += solution(v)
    
    #4-3
    w += ')'
    
    #4-4
    u = u[1:-1]
    reverseU = []
    
    for i in u:
        if i == '(':
            w += ')'
        else:
            w += '('
            
    
    #4-5
    answer = w
    
    

    return answer

 

 

 

결론 

이번 문제에서는 재귀적이라는 단어를 언급했기 때문에 굉장히 간단했습니다. 

 

하지만 대부분의 실전 코딩테스트에서는 따로 재귀적이라는 단어를 언급하지 않고 문제를 내기 때문에

 

그걸 캐치해 내는게 중요한 부분입니다.