[프로그래머스]괄호 변환

삽질을 했던 문제이다.

1. 삽질 

•  올바른 문자열 찾기 -> 모든 ( )가 서로 쌍을 이루는 순서가 맞아야 한다. 나는 그래서 "("을 제일 먼저 찾아야 하니까, "("이 나올때까지 계속 루프를 돌고, "("가 마지막으로 나오면 그 다음 문자열이 ")"임을 확인하고, 해당 "( )"을 pop()시키면 된다고 생각했다. 그래서 이것을 재귀를 돌려서 올바른 문자열이 맞는지 확인하려고 했다.
• 재귀를 돌리는 인자를 선정하는게 어렵다.
  아무리 생각해도 ()쌍을 pop한 후에 다음 재귀를 돌려야 하는데 맨 마지막에는 문자열의 길이가 0이 된다.
  이때 ret한다고 가정하면, 맨 마지막에 ")("만 남는경우에는 예외처리를 어떻게 하는지에 대해 해결하기 어려웠다.
  대부분 이런 경우는 접근 방식이 잘못된 것이다. 그래서 답안을 봤더니 다음과 같이 깔끔하게 해결이 됐다.

def is_balanced_string(s):
    bal = 0
    for p_ in s:
        if p_ == '(':
            bal += 1
        else:
            bal -= 1
    return not (bool(bal))

(가 나오면 +1을 하고, )가 나오면 -1을 한다. 만약에 올바른 문자열이라면 +1과 -1을 한 결과가 음수가 나올 수 없다. 왜냐면 음수가 나오면 )의 개수가 더 많아지는 순간이 온다는 뜻이고 그렇게 되면 올바른 문자열이 될 수 없다.

왜 이런생각을 못했을까 싶었다... 별건 아니지만 암튼 못했다...

 

2. 의문

solution 함수에 if문을 거쳐야먄 u,v 문자열이 할당되도록 로직을 작성했는데 아래 2개의 예시를 보면 차이가 있다.
- 내가 작성한 예시
이렇게 하면 u, v가 할당되기 전에 참조해서 오류가 난다.

def convert_balanced_string(s):
    for i in range(2, len(s) + 1, 2):
        if is_balanced_string(s[:i]):
            u, v = s[:i], s[i:]
            break
    if is_right_string(u):
        return u + convert_balanced_string(v)
    else:
        temp = "(" + convert_balanced_string(v) + ")"
        u_ = u[1:-1].replace("(", ")").replace(")", "(")
        return temp + u_
def solution(p):
    if is_right_string(p):
        return p
    else:
        return convert_balanced_string(p)

이것은 오류가 없는 코드

def solution(p):
    if is_right(p) == True:
        return p
    for i in range(2, len(p) + 1, 2):
        if is_balanced(p[:i]) == True:
            u, v = p[:i], p[i:]
            break
    if is_right(u) == True:
        return u + solution(v)
    else:
        result = '(' + solution(v) + ')'
        for i in u[1:-1]:
            if i == '(':
                result += ')'
            else:
                result += '('
        return result

여기서는 오류가 안생긴다. 왜지..? 똑같이 if문에 들어가야 u,v가 할당되는데 무슨 차이일까..? 이해가 안가서 디버깅하면서 하나하나 살펴보고 있다. 내가 분명 어떤 개념을 모르는 것이다...
이것도 정말 황당한 실수였다..
convert_balanced_string(s) 함수에는 올바른 문자열이 맞으면 바로 return 해주는 로직이 없어서 발생했다. 재귀를 돌다가 ()와 같음 문자가 u로 할당되면, 바로 리턴되어야 하는데 여기서 또 for루프를 돈 것이다. 그러다가 이런 상황이 발생했다.

빈 문자열이 올바른 문자열이 맞는지 확인하는 부분에 다다른것. 루프를 돌지 않고 바로 나와버려서 u,v가 할당이 안되었다.
내가 짠 코드가 분명 이상이 없다면, 꼭 문제를 꼼꼼히 읽어보면서 놓친 부분이 없는지 알아봐야 한다.

 

3. 해석

문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 이게 도대체 무슨 소리인지 몰랐다. u,v가 균형잡힌 괄호 문자열이 될 수 없을때까지 분리해야 된다는건지...? 질문 게시판을 보고 해결했다.
for i in w 해서 한개씩 붙이면서 체크하다가 처음으로 "균형잡힌 괄호 문자열" 이 되면 이를 u 라고 하고 남은 부분은 v라고 하고, v는 빈 문자열이 될수 있다는 뜻임 balanced u를 기준으로 하고 남은 부분은 v 라고 한다는 해석을 너무 줄였다.

아무튼 이렇게 기나긴 방황을 하고, 결국 답안지를 봐서 해결했던 문제이다. 전체 소스 코드는 다음과 같다. 이 문제에서는 재귀함수가 사용되었다. dfs는 아님.

재귀함수는 문제에 주어진 그대로 코드로 옮기면 된다.

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

 

def is_balanced(p):
    bal = 0
    for p_ in p:
        if p_ == '(':
            bal += 1
        else:
            bal -= 1
    return not (bool(bal))

def is_right(p):
    bal = 0
    if is_balanced(p) == False:
        return False
    for p_ in p:
        if p_ == '(':
            bal += 1
        else:
            bal -= 1
        if bal < 0: return False
    return True
    
def solution(p):
    if is_right(p) == True:
        return p
    for i in range(2, len(p) + 1, 2): # 2번 부분
        if is_balanced(p[:i]) == True:
            u, v = p[:i], p[i:]
            break
    if is_right(u) == True: # 3번 부분
        return u + solution(v)
    else: # 4번 부분
        result = '(' + solution(v) + ')'
        for i in u[1:-1]:
            if i == '(':
                result += ')'
            else:
                result += '('
        return result