1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from collections import Counter

# 균형잡힌 괄후 문자열인지 확인하는 함수
def check_balance(k):
    arr = Counter(k)
    if arr['('] == arr[')']:
        return True
    return False

# 올바른 괄호 문자열인지 확인하는 함수
def check_right(k):
    while '()' in k:
        arr = list(k)
        for i in range(len(k)-1):
            if arr[i] == '(' and arr[i+1] == ')':
                arr[i] = arr[i+1] = ''
        k = ''.join(arr)
    if not len(k):
        return True
    return False

# 변환과정을 나타내는 함수
def process(x):
    # 1단계
    if not x:
        return x
    
    # 2단계
    for i in range(1,len(x)+1):
        tmp = x[:i]
        if check_balance(tmp):
            break
    u = tmp
    v = x[i:]
    
    # 3단계
    if check_right(u):
        # 3-1단계
        return u + process(v)
    # 4단계
    else:
        # 4-1, 4-2, 4-3단계
        new = '(' + process(v) + ')'
        arr = []
        # 4-4단계
        for i in range(1,len(u)-1):
            if u[i] == '(':
                arr.append(')')
            else:
                arr.append('(')
        new += ''.join(arr)
        # 4-5단계
        return new

def solution(p):
    answer = ''
    u = ''
    answer = process(p)
    return answer