[프로그래머스] 괄호 변환 - 자바스크립트

문제

코딩테스트 연습 - 괄호 변환

 

풀이

문제가 상당히 길지만 당황하지 말고 천천히 읽어보면 의외로 쉽게 풀리기도 한다.

핵심 키워드는 다음과 같다.

 

균형잡힌 괄호 문자열 : 두 괄호 "("  ")"의 개수가 같다.
올바른 괄호 문자열 : 균형잡힌 괄호 문자열이면서, "("  ")" 의 순서 짝이 맞는 경우이다.

 

임의의 "균형잡힌 괄호 문자열" p를 입력받아 "올바른 괄호 문자열"로 바꿔서 출력하는 문제이다.

 

풀이 방향

문제를 보면, 임의의 p를 입력받으나 이는 이미 "균형잡힌 괄호 문자열"임이 명시되어 있다.
문제에서 등장하는 w가 "균형잡힌 괄호 문자열"이므로 임의의 입력 p를 미리 w로 취급해도 된다.

 

문자열 w로부터 시작되는 알고리즘은 다음과 같다.

 

 

 

1. w가 비었으면 빈 문자열을 반환한다.

 

2. 문자열 w를 순회하면서 "균형잡힌 문자열"까지의 인덱스 i를 찾고, 0~i번째까지를 문자열 u, i~끝까지를 문자열 v로 분리한다.
slice 메서드를 이용할 것인데, slice 메서드의 인자가 문자열의 범위를 벗어나면 빈 문자열이 반환되므로 v는 빈 문자열이 될 수도 있다.

 

3 문자열 u가 "올바른 괄호 문자열" 이면 3-1, 아니라면 3-2를 수행한다.

 

3-1 재귀함수에 인자 w로 문자열 v를 넣은 결과를 문자열u 뒤에 이어 붙여 반환한다.

 

3-2 아래의 과정을 수행한다.
재귀함수에 인자 w로 문자열 v를 넣어 결과를 반환받는다.
문자열 u의 처음, 마지막 문자를 제거하고, 나머지 문자열에서 모든 괄호를 반대방향으로 바꾼다.
"("  solution(v)  ")"  변화된 문자열 u 을 이어 붙여 반환한다.

 

다음의 명령을 수행하도록 코드를 작성하면 된다.

 

코드

function solution(w) {
  if (w === "") return ""; // w가 빈 문자열이면 빈 문자열을 반환한다.
  let u, v;
  let cnt = 0;

  const wLen = w.length;
  for (let i = 0; i < wLen; i++) {
    w[i] === "(" ? cnt++ : cnt--;
    if (cnt === 0) {
      u = w.slice(0, i + 1);
      v = w.slice(i + 1);
      break;
    }
  } // w에서 균형잡힌 문자열까지 문자열 u로 선언하고, 나머지를 v로 선언한다.

  const uLen = u.length;
  for (let i = 0; i < uLen; i++) {
    u[i] === "(" ? cnt++ : cnt--;
    if (cnt < 0) { // cnt < 0 이면 올바른 문자열이 아니므로 3-2를 수행한다.
      let str = "";
      str += `(${solution(v)})`;
      for (let j = 1; j < uLen - 1; j++) {
        u[j] === "(" ? (str += ")") : (str += "(");
      }
      return str;
    }
  }

  return u + solution(v); // 이 3-1의 리턴이 수행되려면 u가 올바른 문자열이어야 한다.
}