프로그래머스 - 괄호 변환 JS

문제

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

문제를 정리해보면

• 주어지는 문자열 p는 항상 '('와 ')'의 갯수가 같은 '균형잡힌 문자열'이다
• 문자열을 '균형잡힌 문자열'인 u와 v로 분리할 수 있는데, u는 항상 '균형잡힌 문자열'로 더이상 분리할 수 없어야 함
• v의 경우 빈 문자열이 될 수 있음
• 가장 중요한 것은 분리된 v에 대해서는
  1단계부터 재귀적으로 실행 이라는 표현인데, 분리된 v를 다시 조건에 맞게 u,v로 분리하는 과정을 반복해야 함
• 그렇다면 이 재귀함수가 return될 때는 ? v가 더 이상 분리될 수 없을 때

예시에서 나온 "()))((()"을 예로 들면
문자열을 분리할때는 분리된 두 값 모두 '균형잡힌 문자열'의 조건을 충족해줘야 하기 때문에 당연히 길이가 홀수일 수는 없으니 짝수 개수로 분리해줘야 함(p 또한 항상 짝수)

u는 빈 문자열이 될 수 없기 때문에 전체 문자열 p에서 2,4,6,...을 기준으로 slice를 하며 u가 '균형잡힌 문자열'로 더이상 분리할 수 없어야 함' 이라는 조건을 만족하는 경우를 찾아주면 됨

p = "()))((()"
u = p.slice(0,2) //"()"
v = p.slice(2) //"))((()"

u가 '올바른' 문자열인 건 사실 지금 중요한건 아니고, v를 다시 분리할 수 있는지를 다시 살펴보면

p = "))((()"
u = p.slice(0,4) // "))(("
v = p.slice(4) // "()"

이 경우에는 (0,2)의 경우 u가 균형 조건을 충족하지 못하기 때문에, index를 늘려서 찾아줌

p = "()"
u = p.slice(0,2) // "()"
v = p.slice(2) // ""

이제 v를 더 이상 분리할 수 없기 때문에, 문자열 v에 대해서 1단계부터 다시 수행한 값은 ""가 됨

u가 올바른 문자열이기 때문에, 이 경우의 반환값은 "()"가 됨 => 이 반환값은 second의 v의 반환값

그렇다면 올바른 문자열이 아닌 "))(("와 "()"를 구한 값은 first의 v의 반환값이고, first의 u와 같이 구해주면 정답

한마디로 u와 v를 분리했을 때, v를 또다시 분리하면서 이때 u의 값을 기억하고 있다가 v를 더이상 쪼개지 못하게 되었을 때 거슬러 올라가면서 구해주면 됨

function solution(p) {
   //u가 올바르던 아니던 v를 재귀적으로 u/v로 다시 분리하는건 똑같음
   const checkCorrect = (str) => {
       const stack = []
       for(const s of str){
           //짝 없으면 stack 넣기
           if(stack.at(-1) === '(' && s === ')'){
               stack.pop()
           }
           else{
               stack.push(s)
           }
       }
       return stack.length ? false : true
   }
   if(checkCorrect(p)){return p}
   const checkNums = (str) => {
       let sum = 0
       for(let s of str){
          sum = s === '(' ? sum +1 : sum - 1
       }
       return sum === 0 || !str.length ? true : false
   }
   //split이라는 함수는 그냥 나눠주는 역할만 함
   const revert = (str) => {
       str = str.split('')
       str.shift()
       str.pop()
       let a = ''
       for(let s of str){
           if(s === ')'){a+='('}
           else{a += ')'}
       }
       return  a 
   }
   let result = 0
   const split = (str,idx,acc) => {
      const u = str.slice(0,idx)
      const v = str.slice(idx)
      //분리될 수 없는 u를 찾기
      //균형잡힌걸 찾았으면 거기서 v를 다시 쪼개기
      if(!v.length){//v를 쪼갤 수 있을 때까지 쪼갰으면 거꾸로 계산
          acc.push(u)
          let str = ''
          for(let i=acc.length-1;i>=0;i--){
              if(checkCorrect(acc[i])){
                  str = acc[i] + str
                  continue
              } else {
                  let empty = '('
                  empty += str + ')'
                  empty += revert(acc[i])
                  str = empty
              }
          }
          result = str
          return
      }
      if(checkNums(u) && checkNums(v)){
          //u가 더이상 분리될 수 없고, v도 개수 맞으면 v를 재귀적으로 다시 쪼개기
          split(v,2,[...acc,u])
      }else{
          split(str,idx+2,[...acc])
      }


      }
       split(p,2,[])
       return result
   }

checkNums()는 '균형잡힌 문자열'을 검사하는 함수
checkCorrect()는 '올바른 문자열'을 검사하는 함수

p를 u와 v로 분리했을 때 두 값 모두 checkNums를 통과하면 -> u의 값을 기록하고 p를 v로 바꾸면서 다시 재귀함수 실행

통과하지 못했다면 똑같은 조건에서 index만 늘려서 다시 실행 -> 만약 p에서 u와 v를 분리할 수 없다면 v의 길이가 0이 되면서 리턴될거임

v의 길이가 0이 되었을 때 -> 앞서 계산했던 u를 가지고 u가 올바른지 아닌지에 따라 문자열을 계속해서 구해주면 됨

총평

뭔가 코드에 허점이 많아보이는데 의외로 통과돼서 신기했음
질문 보니까 진짜 그냥 제시해준 과정대로만 코드짜면 된다던데 진짜 맞는거같음