[코테] 2020 카카오 공채 (괄호 변환)

구현 문제.

알고리즘을 그대로 줄 때는 원리를 너무 고민하지 말고 시키는 대로 빠르게 하는 것도 중요할 것 같다.

 

def solution(p):
    # divide p into u, v.
    def div(p): # return (u, v)
        lparen, rparen = 0, 0
        idx = 0
        for ch in p:
            if ch == '(': lparen += 1
            else: rparen += 1
            if lparen == rparen: break
            idx += 1
        return (p[:idx+1], p[idx+1:])
    
    # check if p is balanced
    def check_balance(p): # return True if p.isempty()
        lparen, rparen = 0, 0
        for ch in p:
            if p == '(': lparen += 1
            else: rparen += 1
        if lparen == rparen: return True
        else: return False
    
    # check if p is correct
    def check_correct(p): # return True if p.isempty()
        if p == '': return True
        stack = [p[0]]
        for ch in p[1:]:
            if not stack: return False
            if ch == '(': stack.append(ch)
            else: stack.pop()
        if stack: return False
        else: return True
    
    # delete first and last char of u, and change all parenthesis
    def slice_and_reverse(u):
        if len(u) < 3: return ''
        lu = list(u[1:len(u)-1])
        
        for i in range(len(lu)):
            if lu[i]=='(': lu[i]=')'
            else: lu[i]='('
        
        return ''.join(lu)
      
    # if p.isempty()
    if p == '': return ''
    
    u, v = div(p)
    if check_correct(u):
        return u + solution(v)
    else:
        return '(' + solution(v) + ')' + slice_and_reverse(u)