def is_correct(src):
    left = 0; right = 0
    # 반대괄호가 먼저나온다면 잘못된 괄호문자열
    if src[0] == ')':
        return False
    else:
        # 왼쪽일경우
        left = left + 1
        for i in src:
            # 오른쪽괄호가 왼쪽보다 많아지는순간이 있는경우 잘못된괄호문자열
            if left < right:
                return False
            elif i == '(':
                left = left + 1
            elif i == ')':
                right = right + 1
        # 이상없을시 올바른 괄호문자열
        return True


def correction(src):
    # 1. 입력이 빈 문자열
    if len(src) == 0:
        return ''
    # index 설정
    idx = 0; left = 0; right = 0
    for i in range(len(src)):
        # 균형잡힌 문자열 체크
        if src[i] is '(':
            left = left + 1
        elif src[i] is ')':
            right = right + 1
        # 균형잡힌만큼 index 를 저장
        if left == right:
            idx = i + 1
            break
    # 2. u와 v로 분리
    u = src[0:idx]; v = src[idx:]

    # 3. u가 올바른 문자열이면 v에 대해 recursive
    if is_correct(u):
        # 3-1 수행한 결과 문자열을 u에 이어붙인후 반환
        return u + correction(v)
    # 4. u 가 올바르지 않다면
    else:
        # 4-1 ~ 4-3 빈문자열에 ( 추가후 v계산후에 )붙여넣기
        tmp = '(' + correction(v) + ')'
        # 4-4 나머지 문자열 뒤집기
        for i in range(1, len(u) - 1):
            if u[i] is '(':
                tmp = tmp + ')'
            else:
                tmp = tmp + '('

        return tmp


def solution(p):
    return correction(p)

'Coding Test' 카테고리의 다른 글

2020 카카오 1차 코딩 테스트 문제 1번  (0) 2019.11.07

+ Recent posts