괄호변환, 2020 카카오 블라인드 채용
균형잡힌 괄호 문자열 : (과 )의 개수가 같은 문자열
올바른 괄호 문자열 : '균형잡힌 괄호 문자열'이면서 (과 )의 짝이 맞는 문자열

문제에서 제시된 '올바른 괄호 문자열'만들기 알고리즘은 다음과 같다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
   4-3. ')'를 다시 붙입니다.
   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
   4-5. 생성된 문자열을 반환합니다.

알고리즘이 생소해서 어려워 보일수 있으나, 하라는대로 하면 풀 수 있다. 단계별로 코드를 옮기면 다음과 같다.

Step 1

빈 문자열이면 그대로 반환하기

# Step 1
if p == '':
    return ''

Step 2

'올바른 괄호 문자열'이라면 스택을 이용할 수 있다. 하지만 '균형잡힌 괄호 문자열'을 판단하는 방법은 단순히 (와 )의 개수만 같으면 된다.
u는 가장 짧은 '균형잡힌 괄호 문자열'임에 주의한다.
아래 코드는 어쩌다 보니 '올바른괄호문자열'을 판단하기 위해 스택을 활용하였으나, 문제에서 '올바른 괄호 문자열'만 입력으로 주어지므로 스택까지 이용하지 않고 '올바른 괄호 문자열'인지 확인할 수 있다. (모범코드 참고)

# Step 2
left, right = 0, 0 # '(', ')'의 개수
u, v = '', ''
flag = 0 # u가 균형잡힌 문자열인지 flag처리
st = []  # (, )를 넣을 스택

for c in p:
    # u와 v를 구분하여 괄호를 붙이기
    # u가 아직 균형잡힌 문자열이 아닐때, u에 계속 괄호를 붙인다
    if flag == 0:
        u += c
    # u가 균형잡힌 문자열일때, 나머지 괄호를 v에 붙인다
    else:
        v += c
    
    # 아직 u는 균형잡힌 문자열이 아닐때, 스택에 괄호를 넣으면서 확인
    if flag == 0:
        if len(st) == 0:
            st.append(c)
        else:
            if st[-1] == '(' and c == ')':
                st.pop()
            else:
                st.append(c)
   
   # (와 )의 개수를 판단하기
    if c == '(':
        left += 1
    else:
        right += 1
    if left == right:
        flag = 1

Step 3

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

# Step 3
# u가 올바른 괄호 문자열이라면, u + (v를 다시 step1부터 수행)
if flag == 1 and len(st) == 0:
    return u + solution(v)

Step 4

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
   4-3. ')'를 다시 붙입니다.
   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
   4-5. 생성된 문자열을 반환합니다.

# Step 4

# Step 4-4
# u의 첫번째, 마지막을 제거하고 나머지 문자열의 괄호를 뒤집는다.
substr = ''
    idx = -1
    for c in u:
        idx += 1 # 문자열 인덱스 증가
        
        # 첫번째, 마지막 문자 제거
        if idx == 0 or idx == len(u) - 1:
            continue
            
        # 나머지 문자열의 괄호방향을 뒤집어서 붙인다
        if c == '(':
            substr += ')'
        else:
            substr += '('


    # Step 4-1 : tmp = '('
    # Step 4-2 : tmp += solution(v)
    # Step 4-3 : tmp += ')'
    # Step 4-4 : tmp += substr
    tmp = '(' + solution(v) + ')' + substr
    
    # Step 4-5 : 생성된 문자열 반환
    return tmp

내 코드 리뷰

느낀점 - 문자열을 처리할때 깔끔하지 못하고 C/C++처럼 반복문을 통해 접근하는것이 마음에 들지 않았다.
그리고 Step4-4에서 substr = u[1:len(u)-1]로하면 u의 길이가 2일때 제대로 되지 않아서 이렇게 짠것도 맘에 들지 않는다. 다른 깔끔한, pythonic한 방법이 있을것이다. 이렇게 짤거였으면 C++로 했지

모범답안, 모범코드

다들 Step별로 함수를 만들어서 해결한 듯 하다. 하지만 제일 위에 뜨는 코드는 아주 짧고 파이썬스럽다.

def solution(p):
    if p == '':
        return p
    # r : u가 균형잡힌 괄호 문자열인지 확인하는 변수, True/False
    # c : (와 )의 개수를 상쇄시킨다. c == 0이면 균형잡힌 괄호문자열이다.
    # 양수면 )가, 음수면 (가 많다.

    r = True; c = 0
    for i in range(len(p)):
        if p[i] == '(':
            c -= 1
        else:
            c += 1
        
        if c > 0:
            r = False
        if c == 0:
            if r:
                return p[:i+1] + solution(p[i+1:])
            else:
                return '(' + solution(p[i+1:]) + ')' + ''.join(list(map(lambda x : '(' if x == ')' else ')', p[1:i])))

파이썬의 문자열 인덱싱, 슬라이싱을 적극 활용한 코드이다.
문자열을 합칠때 join메소드와 lambda식을 이용하여 붙였다.