[programmers] 괄호 변환 (in JS)

문제

괄호변환 - 2020 kakao blind recruitment

Fact

• 균형잡힌 문자열로 더 이상 분리할 수 없는 u가 '올바른 괄호 문자열'인지 확인할 때, 맨 앞에 "("로 시작하면 올바른 괄호 문자열이다.
• 균형잡힌 문자열로 더 이상 분리할 수 없는 u는, u의 처음부터 마지막까지 순회하며 '('일 때 1을 더하고 ')'일 때 1을 빼는 과정 중에 음수가 나올 수 없다.

접근

문자열을 u, v로 분리하고 각 조건에 맞춰 재귀를 통해 문자열을 구한 후 더한다.

• 먼저, 빈 문자열일 경우는 빈 문자열을 바로 반환하도록 한다.
• u와 v를 나누는 과정은 다음과 같다.
  • 처음부터 마지막 문자까지 '('일 때 1을 더하고 ')'일 때 1을 빼면서, 음수가 나오기 전까지가 u이다.
  • 음수가 되는 bracket부터 마지막까지가 v이다.
• u가 올바른 문자열인지는 u의 첫 번째 문자가 '('인지 확인하여 결정한다.'('라면 올바른 문자열이고, ')'라면 올바른 문자열이 아니다.
• u가 올바른 문자열이면 v를 첫 번째 단계를 수행하는 함수에 넣은 후, 그 결과를 u에 덧붙인다.
• u가 올바른 문자열이 아니라면, 아래의 과정을 수행한다.
  • 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙인다.
  • 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다.
  • 4-3. ')'를 다시 붙인다.
  • 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다.
  • 4-5. 생성된 문자열을 반환한다.

복잡도

• 공간 복잡도 : O(N)
  • 최악의 경우 N 만큼의 배열이 필요하게 된다.
• 시간 복잡도 : O(N)

알게된 점

• 첫 번째 loop는 무조건 수행한 후, 조건을 확인하고 싶을 경우 do ... while문을 적용한다.
• 자바스크립트에서도 ++ 연산이 가능하다.
• Array.from은 String.prototype.split("")와 같다.

코드

const isCorrect = (str) => str[0] === "(";

const splitUV = (str) => {
  let i = 0;
  let open = 0;
  do {
    open += str[i++] === "(" ? 1 : -1;
  } while (open !== 0);
  return [str.substring(0, i), str.substring(i)];
};

const reverseBracket = (str) => {
  return Array.from(str)
    .map((bracket) => (bracket === "(" ? ")" : "("))
    .join("");
};

const incorrectStrHandler = (u, v) => {
  return `(${solution(v)})${reverseBracket(u.substring(1, u.length - 1))}`;
};

function solution(p) {
  if (p.length === 0) {
    return p;
  }
  const [u, v] = splitUV(p);
  if (isCorrect(u)) {
    return u + solution(v);
  }
  return incorrectStrHandler(u, v);
}