2020 KAKAO BLIND RECUITMENT 괄호 변환

이 문제에 적힌 그대로 구현하는게 중요하다. 간단한 조건도 잘 체크하자.

 

먼저 '(', ')'로만 이루어진 문자열이 있을 경우 '('의 개수와 ')'의 개수가 같으면 이를 균형잡힌 괄호 문자열이라 한다. 그러면 일단 여기서 체크할 부분은 빈 문자열은 균형잡힌 괄호 문자열이 아니다. 

 

균형잡힌 괄호 문자열을 판별하는 함수를 작성해보자. 함수 이름은 checkIsBalancedString이 좋은 것 같다. 만약 균형잡힌 문자열이라면 true, 아니라면 false를 반환한다.

 

function checkIsBalancedString(s) {
  if (s === "") return false // 빈 문자열은 균형잡힌 문자열이 아니다.

  let left = 0 // 왼쪽 괄호의 개수
  let right = 0 // 오른쪽 괄호의 개수

  for (const char of s) {
    if (char === "(") left++
    else if (char === ")") right++
    else {
      return false // 다른 문자가 포함되어 있다면 균형잡힌 문자열이 아니다.
    }
  }

  return left === right
}

 

이제 올바른 문자열에 대해서 이야기해보자. 올바른 문자열이 되기위한 조건은 일단 균형잡힌 문자열이어야 한다. 그리고 이제 괄호의 쌍이 맞아야한다. 괄호의 쌍에 관한 문제에서는 자연스럽게 스택을 떠올리게 된다. 올바른 문자열을 체크하는 함수의 이름은 checkIsRightString으로 하기로 했다.

 

function checkIsRightString(s) {
  if (!checkIsBalancedString(s)) {
    return false
  }

  const stack = []

  for (const char of s) {
    if (stack.length === 0) {
      stack.push(char)
      continue
    }

    if (stack.at(-1) === "(" && char === ")") {
      stack.pop()
    } else {
      stack.push(char)
    }
  }

  return stack.length === 0 ? true : false
}

 

문제에서 p는 균형잡힌 문자열이라고 했고 균형잡힌 문자열은 올바른 문자열이 될 가능성이 존재한다. 그 다음에 1~4-5에 해당하는 알고리즘 로직을 algo라는 함수로 추출했다. 코드를 작성하면 아래와 같다.

 

function solution(p) {
  if (checkIsRightString(p)) {
    return p
  }
  return algo(p)
}

 

 algo함수는 문제에서 주어진 알고리즘에 따라 차분하게 구현하는게 필요하다.

 

function algo(s) {
  // 1. 입력이 빈 문자열인 경우 빈 문자열을 반환한다.
  if (s === "") return s

  // 2. 문자열 w를 두 균형잡힌 괄호 문자열 u와 v로 분리한다.
  return divide(s)

  function divide(s) {
    // s는 일단 이미 균형잡힌 문자열임 근데 이걸 나눌꺼임
    // u, v인데 u는 균형잡힌 문자열로 더이상 분리될 수가 없음, v는 빈문자열이 될 수 있음

    for (let i = 0; i <= s.length; i++) {
      const u = s.slice(0, i)
      const v = s.slice(i)

      // 2. 문자열 w를 두 균형잡힌 괄호 문자열 u와 v로 분리한다.
      if (checkIsBalancedStringWhichCanNotDivide(u) && (checkIsBalancedString(v) || v === "")) {
        // 단 u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야하며 v는 빈 문자열이 될 수도 있다.
        // 3. u가 올바른 괄호 문자열이라면 문자열 v에 대해 1단계부터 다시 수행한다.
        if (checkIsRightString(u)) {
          // 3.1 수행 결과를 u에 이어 붙인 후 반환한다.
          return u + algo(v)
        } else {
          // 4. 문자열 u가 올바른 괄호 문자열이 아니라면 아래 과정을 수행한다.
          let temp = ""
          temp += "("
          temp += algo(v)
          temp += ")"
          temp += Array.from(u.slice(1, -1))
            .map((x) => {
              if (x === "(") return ")"
              else if (x === ")") return "("
            })
            .join("")

          return temp
        }
      }
    }
  }
}

 

빈 문자열이면 바로 반환하는 조건을 따른 후에 바로 균형잡힌 문자열을 u,v로 나눠야한다. 이 때 자연스럽게 나누는 로직을 담은 divide라는 함수로 추출했다. p의 길이는 1000이하이기 때문에 완전 탐색하기로 했다. divide 함수를 보면 그냥 i를 쭉 이동 시키면서 u와 v를 분리한다. 하지만 u와 v를 분리한 후에 문제에서 주어진 조건에 따라 u는 더 이상 분리할 수 없는 균형잡힌 문자열이어야하며, v는 빈 문자열 또는 균형잡힌 문자열이어야 한다. 그래서 더이상 분리할 수 없는 균형잡힌 문자열을 체크하는 함수를 추출했다. 

 

function checkIsBalancedStringWhichCanNotDivide(s) {
  if (!checkIsBalancedString(s)) {
    return false
  }

  let flag = true

  for (let i = 0; i < s.length; i++) {
    const left = s.slice(0, i)
    const right = s.slice(i)

    if (checkIsBalancedString(left) && checkIsBalancedString(right)) {
      flag = false
      break
    }
  }

  return flag
}

 

더 이상 분해할 수 없는 함수의 로직은 간단하다. flag 변수가 있고 왼쪽 오른쪽을 나눴을 때 나눌 수 있다면 flag를 false 처리한다. 이러면 u와 v를 나눌 수 있는 조건을 체크할 수 있다. 

 

나누었다면 뭐를 하는가? 문제의 조건에 따라 아래와 같이 u가 올바른 문자열인지 처리한다.

 

        // 단 u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야하며 v는 빈 문자열이 될 수도 있다.
        // 3. u가 올바른 괄호 문자열이라면 문자열 v에 대해 1단계부터 다시 수행한다.
        if (checkIsRightString(u)) {
          // 3.1 수행 결과를 u에 이어 붙인 후 반환한다.
          return u + algo(v)
        } else {
          // 4. 문자열 u가 올바른 괄호 문자열이 아니라면 아래 과정을 수행한다.
          let temp = ""
          temp += "("
          temp += algo(v)
          temp += ")"
          temp += Array.from(u.slice(1, -1))
            .map((x) => {
              if (x === "(") return ")"
              else if (x === ")") return "("
            })
            .join("")

          return temp
        }

 

 올바른 문자열이면 v에 대하여 1단계부터 수행한 결과를 u에 이어붙여서 반환하니까 u + algo(v)로 나타낼 수 있다.

올바른 문자열이 아니라면 4번의 과정을 수행한다. 

 

전체 코드는 다음과 같다.

 

function solution(p) {
  if (checkIsRightString(p)) {
    return p
  }
  return algo(p)
}

function algo(s) {
  // 1. 입력이 빈 문자열인 경우 빈 문자열을 반환한다.
  if (s === "") return s

  // 2. 문자열 w를 두 균형잡힌 괄호 문자열 u와 v로 분리한다.
  return divide(s)

  function divide(s) {
    // s는 일단 이미 균형잡힌 문자열임 근데 이걸 나눌꺼임
    // u, v인데 u는 균형잡힌 문자열로 더이상 분리될 수가 없음, v는 빈문자열이 될 수 있음

    for (let i = 0; i <= s.length; i++) {
      const u = s.slice(0, i)
      const v = s.slice(i)

      // 2. 문자열 w를 두 균형잡힌 괄호 문자열 u와 v로 분리한다.
      if (checkIsBalancedStringWhichCanNotDivide(u) && (checkIsBalancedString(v) || v === "")) {
        // 단 u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야하며 v는 빈 문자열이 될 수도 있다.
        // 3. u가 올바른 괄호 문자열이라면 문자열 v에 대해 1단계부터 다시 수행한다.
        if (checkIsRightString(u)) {
          // 3.1 수행 결과를 u에 이어 붙인 후 반환한다.
          return u + algo(v)
        } else {
          // 4. 문자열 u가 올바른 괄호 문자열이 아니라면 아래 과정을 수행한다.
          return (
            "" +
            "(" +
            algo(v) +
            ")" +
            Array.from(u.slice(1, -1))
              .map((x) => {
                if (x === "(") return ")"
                else if (x === ")") return "("
              })
              .join("")
          )
        }
      }
    }
  }
}

function checkIsBalancedStringWhichCanNotDivide(s) {
  if (!checkIsBalancedString(s)) {
    return false
  }

  let flag = true

  for (let i = 0; i < s.length; i++) {
    const left = s.slice(0, i)
    const right = s.slice(i)

    if (checkIsBalancedString(left) && checkIsBalancedString(right)) {
      flag = false
      break
    }
  }

  return flag
}

function checkIsBalancedString(s) {
  if (s === "") return false // 빈 문자열은 균형잡힌 문자열이 아니다.

  let left = 0 // 왼쪽 괄호의 개수
  let right = 0 // 오른쪽 괄호의 개수

  for (const char of s) {
    if (char === "(") left++
    else if (char === ")") right++
    else {
      return false // 다른 문자가 포함되어 있다면 균형잡힌 문자열이 아니다.
    }
  }

  return left === right
}

function checkIsRightString(s) {
  if (!checkIsBalancedString(s)) {
    return false
  }

  const stack = []

  for (const char of s) {
    if (stack.length === 0) {
      stack.push(char)
      continue
    }

    if (stack.at(-1) === "(" && char === ")") {
      stack.pop()
    } else {
      stack.push(char)
    }
  }

  return stack.length === 0 ? true : false
}

 

문제를 한 줄 한 줄 읽으며 복잡한 로직을 만나면 최대한 함수가 하나의 역할만 하도록 추출을 하면서 풀었다. 최근에 리팩토링 책을 조금씩 읽고 있는데 함수 추출하고 함수 인라인하고 이런 리팩토링하는 재미가 쏠쏠하다.