문제 설명

전체 코드

def solution(p):
    def isgalho(s):
        answer = []
        for i in s:
            if len(answer) == 0:
                answer.append(i)
            else:
                if answer[-1] == "(":
                    if i == ")":
                        answer.pop()
                    else:
                        answer.append(i)

        if answer:
            return False
        else:
            return True


    def dfs(w):
        if len(w) == 0:
            return ""

        u = ""
        v = ""

        for i in range(len(w)):
            if len(u) == 0:
                u += w[i]
            else:
                if u.count('(') == u.count(')'):
                    v += w[i:]
                    break
                else:
                    u += w[i]

        if isgalho(u):
            return u + dfs(v)
        else:
            u = list(u)
            for i in range(len(u)):
                if u[i] == ')':
                    u[i] = "("
                elif u[i] == '(':
                    u[i] = ")"

            u = ''.join(u)
        return "(" + dfs(v) + ")" + u[1:-1]

    return dfs(p)

해결 방법

처음 이 문제를 풀었을 때가 8개월 전인거 같다 그 때는 왜 level2지? level3도 될거 같은데 라고 했다. 하지만 지금 다시 풀어보면서 이 문제는 level2가 적당한 것 같다. 그 이유는 내가 생각할거 없이 문제에서 모든 해답을 주고 있고 문제에서 하라는 대로 하면 정답이 나오기 때문이다.

이 문제에서 요구하는 것은 구현능력과 간단한 재귀를 사용할 수 있느냐 없느냐 하는 것이다. 코드를 살펴보자.

먼저 p를 dfs라는 함수에 집어 넣자 문제에서 문자열 w라고 했으므로 dfs에 매개변수로 w라고 하였다.

1. w가 비었는지 확인 한다. len(w) == 0: 비어있으면 return ""

2. u와 v 변수를 만들어 매개변수 w를 for문을 돌리며 u의 원소로 집어넣고 만약 u가 "균형잡힌 괄호 문자열"이면 그만 원소로 넣고 나머지를 v에 넣어주고 break

3. isgalho라는 '('와 ')'의 괄호의 짝도 모두 맞을 경우인 "올바른 문자열"인지 판별하는 함수를 만들고 u를 집어넣어 True인지 False인지 판별한다.

   3-1 True라면 u 는 놔두고 v에 대하여 dfs함수를 재귀 시킨다.

4. False라면 일단 u안의 괄호 방향을 뒤집고 "(" + dfs(v) + ")" + u[1:-1]을 return한다.