괄호 변환 (Programmers 60058)

🧑‍💻 괄호 변환

• 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
• 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

용어의 정의

• '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
• 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
• 예를 들어, "(()))("와 같은 문자열은 "균형잡힌 괄호 문자열" 이지만 "올바른 괄호 문자열"은 아닙니다.
• 반면에 "(())()"와 같은 문자열은 "균형잡힌 괄호 문자열" 이면서 동시에 "올바른 괄호 문자열" 입니다.
• '(' 와 ')' 로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열" 이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.

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

• "균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.

매개변수 설명

• p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
• 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
• 만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.

입출력 예제

p	result
"(()())()"	"(()())()"
")("	"()"
"()))((()"	"()(())()"

🧑‍💻 해결방법

• 올바른 괄호인지 확인하는 함수, 올바르지 않은 분기점을 뽑아줄 함수가 필요하다.
• 올바르지 않은 부분을 만났다면 그 부분부터 재귀함수로 돌려준다.
• replace를 활용해서 괄호를 변환해준다.

🧑‍💻 코드

def correction(br):
   stack = []
   for b in br:
       if b == '(':
           stack.append(b)
       else:
           try:
               stack.pop()
           except:
               return False
   if len(stack) == 0:
       return True
   else:
       return False

# 분기점 만들어주기
def split_brack(br):
   cnt = 0
   for idx in range(len(br)):
       if br[idx] == '(':
           cnt += 1
       else:
           cnt -= 1
       if cnt == 0:
           return idx + 1
   return idx + 1

def solution(p):
   answer = ''
   if (p == "") or (correction(p) == True):
       return p

   idx = split_brack(p)
   u, v = p[:idx], p[idx:]

   if correction(u):
       answer = u + solution(v)
   else:
       answer = '(' + solution(v) + ')'
       u = u[1:-1].replace('(', 'a')
       u = u.replace(')', 'b')
       u = u.replace('a', ')')
       u = u.replace('b', '(')
       answer = answer + u

   return answer

🧑‍💻 총평

• 문제를 읽는 것부터가 난관인 문제
• 사람들의 후기를 보면 문제에 주어진대로 따라하면 된다고 하는데 어려웠다.
• 로직을 구현하는 부분 (특히 correction 함수 부분)을 구현하는데에 아직 익숙치가 않아서 암기하다시피 해야할 듯 하다.
• 명확히 다시 느낀 점은 'bracket 문제의 correction', '재귀함수' 를 구현하는 데에 어려움을 항상 느낀다는 점.
• 알고리즘 문제는 문자열이 많이 나오기 때문에 반드시 익혀 습득할 필요가 있다.