알고리즘/코딩 테스트

[카카오] 2020 신입 개발자 블라인드 채용 1차 코딩 - 괄호 변환

망나 2021. 8. 30. 22:12

올바른 괄호 / 균형잡힌 괄호 2가지를 체크하는 함수를 각각 구현한 뒤 문제에서 설명하는 변환 과정 1 ~ 4를 구현 하면 됩니다.

 

이때 재귀 부분만 신경쓰면 큰 어려움은 없을 듯 합니다.

 

def isbalanced(s):
    flag = 0
    for c in s:
        if c == '(':
            flag += 1
        elif c == ')':
            flag -= 1
        
    if flag == 0: return True
    else: return False
    
def iscorrect(s):
    stack = []
    for c in s:
        if len(stack) == 0:
            stack.append(c)
        else:
            if c == '(':
                stack.append(c)
            elif c == ')':
                if len(stack) == 0 or stack.pop() != '(':
                    return False
    
    if len(stack) == 0: return True
    else: return False
    

def solution(p):
    answer = ""
    u = ""
    v = ""
    
    if len(p) == 0 or iscorrect(p): return p
    
    for i in range(2, len(p)+1, 2):
        if isbalanced(p[0:i]):
            u=p[0:i]
            v=p[i:len(p)]
            print(u, v)
            break
    
    if iscorrect(u):
        answer += u + solution(v)
    
    else:
        answer += '(' + solution(v) + ')'
        for c in u[1:-1]:
            if c == '(': answer += ')'
            else: answer += '('
    
    return answer

 

1 2