괄호변환

 

 

이 문제는 DFS나 BFS를 사용하기 보단

구현, 재귀함수와 가까운 듯 하다.

 

코드내에 간단한 조건들과 구현을 정리해보았다.

 

 

 

코드

# 올바른 문자열인지 확인해주는 함수
def test1(array):
    count = 0
    for i in array:
        if i == "(":
            count += 1
        else:
            count -= 1
        if count < 0:
            return False
    return True

# 메인 함수
def solution(array):
	# 길이가 0이면 그대로 반환
    if len(array) == 0:
        return ""
    # 해당 문자열이 균형잡혔는지 확인
    count1,count2 = 0, 0
    for i in range(len(array)):
        if array[i] == "(":
            count1 += 1
        else:
            count2 += 1
        if count1 == count2:
            u = array[0:i+1]
            # 규형이 잡혔지만 u를 제외한 v가 더이상 없는 경우
            if i+1 >= len(array):
                v = ""
                break
            v = array[i+1:]
            break
    # u가 올바른 문자열이면 v처리
    if test1(u):
        v = solution(v)
    # u가 올바르지 않다면 조건에 맞추어 처리
    else:
        mid = ""
        for i in range(1, len(u)-1):
            if u[i] == "(":
                mid += ")"
            else:
                mid += "("
        result = "(" + solution(v) + ")" + mid
        return result
    return u+v


array = "()))((()"
print(solution(array))

 

 

재귀함수를 얼마나 잘읽는지 중요한 문제인듯 싶다.

헷갈릴때는 재귀함수가 많이 호출되는 예시를 사용해 일련의 과정을 따라가는 방식도 괜찮은 것 같다.