📚 Lv2 - 괄호 변환

괄호 변환

이해

• 프로그래머스 문제를 풀 때는 입출력 예제를 보며 문제를 어떻게 풀어야 하는지 감을 익힐 수 있다. (아~ 이렇게 풀어야 겠구나)
• 보통 수학문제 풀때, 예제 문제를 풀어 보며 공식을 적용하면서 익히는 것처럼 말이다.

ex) )(()(

u : ))(( + v : )(

• 올바른 괄호 문자가 아니므로 4번 적용
• 4-1 처음에 ( 붙인다.
• 4-2v를 다시 체크한다.
  • u : )(, v : ``
  • 4-1 처음에 r에 ( 붙인다.
  • 4-2 v를 체크하였을 때 null이므로 통과
  • 4-3 r에 )를 붙인다.
  • 4-4 u의 첫 번째, 마지막 문자 제거 하고, r뒤에 합친다.
  • 4-5 반환
• 4-2 결과 ( + ()
• 4-3 뒤에 )를 붙인다.
• 4-4 u의 첫 번째, 마지막 문자 제거 후, 뒤집기 : (()) + ()
• 4-5 결과 반환

(())()

소스

# u가 올바른 괄호인지 판단하는 함수
def collect_u(u):
    left, right = 0, 0
    for i in u:
        if i == '(':
            left += 1
        else:
            right += 1

        if left < right:
            return False
    return True


# dfs
def dfs(arr):
    if len(arr) == 0:
        return ''
    u, v = [], []
    left, right = 0, 0
    check = False
		
	# u, v 값을 찾기 위한 반복문
    for alpa in arr:
        if alpa == '(':
            left += 1
        else:
            right += 1

        if not check:
            u.append(alpa)
        else:
            v.append(alpa)

        if left == right:
            check = True

	# u가 올바른 괄호인지 판단한다.
    if collect_u(u):
        u = ''.join(u)
        return ''.join(u + dfs(v))
    else:
        r = '('
        r += dfs(v)
        r += ')'
        for i in range(1, len(u) - 1):
            if u[i] == '(':
                r += ')'
            else:
                r += '('
        return r


def solution(p):
    answer = dfs(p)
    return answer