[2020 카카오공채 코딩테스트 2번(괄호 변환) 풀이]

 

카카오 공채 코딩테스트 2번 풀이 글입니다.

 

2번 문제는 설명에 주어진 그대로를 구현하는 문제이며 재귀, 함수에 대한 개념이 명확하게 있어야 풀 수 있습니다.

우선 문제 설명을 이해하는 것이 제일 어려웠습니다. 예시에서 u의 변환 부분이 추가 되는 것이 '('와 ')' 사이인지 뒤인지 모호하게 설명되 있어서 이 부분을 명확하게 캐치하는 것이 핵심입니다. 저는 다양한 테스트 케이스를 직접 확인해가면서 문제의 설명을 정확하게 이해하였습니다. 

 

우선 균형잡힌 괄호 문자열을 파악하는 함수를 만들어 2번을 해결합니다. 애초에 주어진 문자열이 '('와 ')' 의 짝이 맞으므로 저는 문자열 처음 부터 (의 개수와 ) 을 각각 카운트하여 같게 되는 지점을 균형잡힌 문자열 u가 된다고 가정하였습니다. 예를 들어 (())))인 경우 (()) 까지 갔을 때 ( 개수 2, )의 개수 2인 상황에 균형잡힌 상태라고 정의하였습니다.

 

이후 올바른 괄호 문자열을 파악하는 방법은 )가 나오면 -1을 하고 ( 가 나오면 +1 을 해주는 변수 하나를 모니터링 했습니다. 애초에 균형잡힌 문자열을 대상으로 체크하는 것이기에 ))(( 와 같은 것을 걸러내면 됩니다. 즉, ))(( , )(, (()), ))()(( 와 같은 것들을 대상으로 진행하기 때문에 누적된 ) 의 개수가 ( 의 개수보다 많아지게 되면 올바르지 않은 경우가 됩니다. 위의 언급한 ))((, )(, ))()(( 가 되겠습니다. )()( 와 같은 것들은 고려하지 않아도 됩니다. 왜냐하면 균형잡힌 문자열이 아니기 때문입니다.

 

이렇게 하여 3번과 4번을 구분하는 코드를 완성할 수 있습니다. 여기까지 만든 함수들을 이용하여 코드를 작성하면 완성됩니다. 

 

문제 출처

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

 

코드 

def solution(p):
    
    # step 1.
    if not p:
        return p
    
#     p = "))(())(("
    
    answer = convert(p)
    
    return answer

def convert(string):

    #empty string 
    if string =="":
        return ""
    
    # step 2
    u = ""
    v = ""
    
    left_cnt = 0
    right_cnt = 0
    i = 0
    for i in range(len(string)):
        if string[i] == '(':
            left_cnt += 1
        else:
            right_cnt += 1
        
        if left_cnt == right_cnt:
            break
    
    u = string[:i+1]
    v = string[i+1:]
    
    # 3. 4.
    if check(u) == True:
        
        res= u+convert(v)
    else:
        res= "(" + convert(v) + ")" + convert(change(u[1:-1]))
    print("u:",u," v:",v)
    return res
# 3
def check(u):
    cnt = 0
    for ch in u:
        if ch == '(':
            cnt += 1
        else:
            cnt -= 1
    
        if cnt < 0:
            return False
        
    return True
            
def change(u):
    string = ""
    for ch in u:
        if ch == '(':
            string += ')'
        else:
            string += '('
    return string