괄호 변환

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/60058

문제에서 알고리즘 주문서를 다음과 같이 따로 준다. 따라서 다른 방식 말고 이대로 풀어야 정확한 결과가 나온다. 그런데 무슨 말인지 못 알아먹겠다...

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. 생성된 문자열을 반환합니다.

도저히 이해가 안 되어서 검색해봤다. 저 주문서를 이해하지 못하는 사람이 나 말고도 많았다. 누군가 쉽게 번역한 것을 찾았다.

1. p가 빈 문자열 일 경우 그대로 리턴
2. p를 '(' 와 ')' 의 개수가 같은 u, 그 나머지인 v로 분리
3-1. u가 닫힌 괄호일 경우
    1번으로 돌아가 p에 v를 넣어(=solution(v)) 결과 받기
    (u+위의 결과) 리턴
3-2. u가 닫힌 괄호가 아닐 경우
    '1번으로 돌아가 p에 v를 넣은(=solution(v)) 결과 임시 저장
    u의 앞뒤 문자를 제거하고 남은 모든 괄호를 뒤집는다( '('는 ')'로 )
    "(" + v + ")" + 뒤집은 결과 를 리턴

아하 이제 잘 알겠다!!

<입력>
<출력>
<예시>

---

나의 풀이

def split_string(string):
    cnt = 0
    is_perfect = True
    for i in range(len(string)):
        if string[i] == "(":
            cnt += 1
        elif string[i] == ")":
            cnt -= 1
        if cnt < 0:
            is_perfect = False
        if cnt == 0:
            return string[:i+1], string[i+1:], is_perfect

def change_u(string):
    for i in range(0, len(string)):
        if string[i] == "(":
            string = string[:i] + ")" + string[i+1:]
        elif string[i] == ")":
            string = string[:i] + "(" + string[i+1:]
    return string[1:-1]
    

def solution(p):
    answer = ""
    if p == "":
        return answer
    u, v, u_is_perfect = split_string(p)
    if u_is_perfect == True:
        answer += u
        p = solution(v)
        answer += p
        return answer
    else:
        p = solution(v)
        return "(" + p + ")" + change_u(u)

---

다른 사람 풀이

def solution(p):
    if p=='': return p
    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]) ))

---

느낀 점

람다 함수를 배우자.