[이코테 Ch13-18] 괄호 변환 (재귀)

👩🏻‍💻문제설명

[이코테 Ch13-18] 괄호 변환 (재귀)

✍️Idea Sketch

문제 요약

균형잡힌 괄호 문자열 : '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같은 경우
올바른 괄호 문자열 : 균형잡힌 괄호 문자열에서 '('와 ')'의 괄호의 짝도 모두 맞는 경우

목표 : 균형잡힌 괄호 문자열을 올바른 괄호 문자열로 변환하기

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

시간복잡도

O(n)

알고리즘 : 재귀 함수 구현

재귀 함수 구현을 요구하는 문제이다. 재귀 함수 구현은 DFS 알고리즘의 핵심이 되기 때문에, 교재에서 DFS/BFS 파트로 분류되었다.

✍️내 소스코드

#1 : 입력이 빈 문자열인 경우, 빈 문자열을 반환한다.

#for문 : 문자열 w를 두 균형잡힌 괄호 문자열 u, v로 분리해야한다. 문자열을 분리하는 기준을 구해야 한다. 열린 괄호와 닫힌 괄호의 개수가 똑같아지는 idx를 구하면 균형잡힌 괄호 문자열 w를 구할 수 있다.

#2 : idx를 기준으로, 문자열 w를 두 균형잡힌 괄호 문자열 u, v로 분리한다.

#3 : 문자열 u가 올바른 괄호 문자열이면, 문자열 v에 대해 재귀 함수를 호출한다. 문자열 u가 올바른 괄호 문자열인지 확인해야한다. 문자열 u는 항상 균형잡힌 괄호 문자열이다. 따라서 인덱스 0의 값이 열린 괄호 (면, 항상 올바른 괄호 문자열이다.

return u + recursion(v)

#4 : 문자열 u가 올바른 괄호 문자열이 아니면, 다음의 과정을 수행한다.

• (를 붙인다 + 문자열 v에 대해 재귀 함수를 호출한다 + )를 붙인다 + temp를 붙인다
• temp : string slice u[1:-1]로 첫번째와 마지막 문자를 제거하고, for문으로 괄호 방향을 뒤집는다.

return '(' + recursion(v) + ')' + temp

전체 코드

  def solution(p):
      return recursion(p)

  def recursion(w):
      if w == '':  # 1
          return ''

      cnt_open = 0
      cnt_close = 0
      idx = len(w)

      for i in range(len(w)):
          if cnt_open == cnt_close > 0:
              idx = i 
              break
          if w[i] == '(':
              cnt_open += 1
          elif w[i] == ')':
              cnt_close += 1

      u = w[:idx]  # 2
      v = w[idx:]

      if w[0] == '(': # 3
          return u + recursion(v)

      else: # 4
          temp = ''

          for x in u[1:-1]:
              if x == ')':
                  temp += '('
              else:
                  temp += ')'

          return '(' + recursion(v) + ')' + temp