2020 KAKAO BLIND RECRUITMENT 괄호 변환 (js)

괄호 변환(30) 문제 보기

---

문제 이해

솔직히 문제를 해결하기 전까지 "뒤집고붙이고떼고다시하고..." 뭔 말을 하는건지 당최 이해를 못했습니다.

 

그냥 시키는 대로 코드를 작성하고,

결과를 재귀 형태로 만들었더니 통과할 수 있었습니다.

 

따라서 시키는 대로 코드를 작성한 과정을 풀이로 적어보겠습니다.

문제 풀이

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

    // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if (p === "") {
      return "";
    }

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

// 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
// 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
const divide = (w) => {
  let left = 0;
  let right = 0;
  for (let i = 0; i < w.length; i++) {
    if (w[i] === "(") {
      left++;
    } else {
      right++;
    }

    if (left === right) {
      break;
    }
  }
  const u = w.slice(0, right * 2);
  const v = w.slice(right * 2);
  return [u, v];
};

우선 두 '균형잡힌 괄호 문자열'로 만들 방법을 생각했습니다.

 

for문으로 괄호의 모양별로 "(", ")"의 갯수를 카운트 합니다.

모양별 카운트가 같다면 반복문을 종료합니다.

 

결과를 slice(0, right*2)를 이용해 분리하면

"균형잡힌 괄호 문자열" u와 v로 분리할 수 있습니다.

3번과 4번은 분기처리입니다. 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

      // 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
      // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
const isRightBracket = (bracket) => {
  const stack = [];
  stack.push(bracket[0]);
  let index = 1;

  while (index < bracket.length) {
    if (stack[stack.length - 1] === "(" && bracket[index] === ")") {
      stack.pop();
    } else {
      stack.push(bracket[index]);
    }
    index++;
  }

  return stack.length ? false : true;
};

"올바른 괄호 문자열"인지 판별하기 위한 함수를 만듭니다.

이 함수는 stack을 이용합니다.

최초에 stack에 입력받은 문자열의 첫번째 index에 해당하는 괄호를 넣고,

그다음 index부터는 올바르게 닫히는지 확인합니다. 

 

stack의 top에 있는 괄호가 "("이고 비교 index의 괄호가 ")"라면 올바른 괄호이기 때문에 stack의 top을 제거합니다.

그렇지 않다면 stack에 비교 index를 push합니다.

index++를 하여 나머지 괄호에 대해서도 판별합니다.

 

stack에 문자열이 남아있다면 false를 반환하고,

남아있지 않다면 "올바른 괄호 문자열"이므로 true를 반환하면 됩니다.

3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

  const wornl = (p) => {
    // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if (p === "") return "";

// 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    const [u, v] = divide(p);

    // 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
    //   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
    if (isRightBracket(u)) {
      const result = wornl(v);
      return u + result;
    } else {
      // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행하라고 합니다.

그래서 하라는 대로 재귀로 만들어 주었습니다.

(갑자기 recursion이 생각나지 않아 wornl로 함수명을 지었습니다;;;)

 

그리고 v에 대해 1단계부터 다시 수행한 결과를 u에 이어 붙인후 반환합니다.

4-1. ~ 4-5. 자세한 설명은 주석으로 대체합니다.

    } else {
      // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
      //   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
      let blankString = "(";
      //   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
      const result = wornl(v);
      //   4-3. ')'를 다시 붙입니다.
      let newV = blankString + result;
      //   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
      let rightAddedBracket = newV + ")";
      //   4-5. 생성된 문자열을 반환합니다.
      const finish = rightAddedBracket + flip(u.slice(1, -1));
      return finish;
    }

 

왜 이렇게 해야하는건지 정확하게 이해는 못했지만 하라는대로 합니다.

4-1. "("를 붙입니다.

4-2. 재귀 결과를 이어 붙입니다.

4-3. ")"를 다시 붙입니다.

 

4-4. 에서 나머지 문자열의 괄호 방향을 뒤집는 부분을 함수로 만들어 주었습니다.

      //   4-4. ... 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
const flip = (bracket) => {
  let result = "";
  for (let i = 0; i < bracket.length; i++) {
    if (bracket[i] === "(") {
      result += ")";
    } else {
      result += "(";
    }
  }
  return result;
};

for문을 이용해 ")"는 "("로, "("는 ")"로 만들어준 결과를 반환합니다.

 

4-5. 다 붙인 결과를 반환합니다.

---

이렇게 문제 이해는 덜 된 채로 친절한 안내에 따라 문제를 해결할 수 있었습니다;;; 기쁩니다.

(()())()
()
()(())()

 

주석 제거 및 변수명 약간 정리 코드

const divide = (w) => {
  let left = 0;
  let right = 0;
  for (let i = 0; i < w.length; i++) {
    w[i] === "(" ? left++ : right++;
    if (left === right) break;
  }
  const u = w.slice(0, right * 2);
  const v = w.slice(right * 2);
  return [u, v];
};

const isRightBracket = (bracket) => {
  const stack = [];
  stack.push(bracket[0]);
  let index = 1;

  while (index < bracket.length) {
    if (stack[stack.length - 1] === "(" && bracket[index] === ")") {
      stack.pop();
    } else {
      stack.push(bracket[index]);
    }
    index++;
  }

  return stack.length ? false : true;
};

const flip = (bracket) => {
  let result = "";
  for (let i = 0; i < bracket.length; i++) {
    if (bracket[i] === "(") {
      result += ")";
    } else {
      result += "(";
    }
  }
  return result;
};

function solution(p) {
  const recursion = (p) => {
    if (p === "") return "";
    
    const [u, v] = divide(p);
    
    if (isRightBracket(u)) {
      const recursionResult = wornl(v);
      return u + result;
    } else {
      const leftBracket = "(";
      const recursionResult = wornl(v);
      const newV = leftBracket + wornlResult;
      const rightAddedBracket = newV + ")";
      const finish = rightAddedBracket + flip(u.slice(1, -1));
      return finish;
    }
  };
  return recursion(p);
}

solution("(()())()");
solution(")(");
solution("()))((()");