カッコ/JavaScript/レベル2の変換

📃質問アドレス

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

問題の説明

新しい開発者としてココアに入った「康」は、先輩の開発者から仕事の任務を受け、他の開発者が書いたソースコードを分析し、問題を発見し、修正するように要求された.
ソースコードをコンパイルしてログを表示すると、ほとんどのソースコードのカッコがペアではない形式で記述されているため、エラーが発生します.
変更するソースファイルが多すぎるため、conはソースコードからカッコをすべて抽出し、カッコ文字列を正しい順序で表示するプログラムを開発することを検討しています.
用語定義
文字列が「(」と「)」のみで構成され、「(」の数と「)」の数が同じである場合は、バランスカッコ文字列と呼ばれます.
「(」と「)」のカッコが一致している場合は、正しいカッコ文字列と呼ばれます.
たとえば、文字列「()」(「」など)は「カッコ文字列のバランス」ですが、「有効カッコ文字列」ではありません.
逆に、文字列(()()などは「バランスのとれたカッコ文字列」であり、「正しいカッコ文字列」でもあります.
「(」と「)」のみからなる文字列wが「バランスの取れた括弧文字列」である場合、以下の手順で「正しい括弧文字列」に変換できます.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

パラメータとして「カッコ文字列のバランス」pを指定した場合、解法関数を完了し、指定したアルゴリズムを実行して「正しいカッコ文字列」に変換した結果を返します.
パラメータの説明

pは、2または1000より長い偶数の「(」および「)」のみからなる文字列です.

文字列pを構成する「(」および「)」の数は常に同じである.

pがすでに「正しいカッコ文字列」である場合、戻ることができます.

I/O例

wresult"(()())()""(()())()"")(""()""()))((()""()(())()"
I/O例説明
I/O例#1
すでに「有効な括弧文字列」です.
I/O例#2
2つの文字列u,vを区切る.
u = ")("
v = ""
uは「有効な括弧文字列」ではないため、次のように新しい文字列を作成します.
ステップ1からvの再帰操作を開始すると、空の文字列が返されます.
uの前後文字を削除し、残りの文字のカッコ方向を反転すると、その文字は「」になります.
したがって、生成された文字列は「(+)」「+」「+」「+」であり、最終的に「()」に変換されます.
I/O例#3
2つの文字列u,vを区切る.
u = "()"
v = "))((()"
文字列uを「有効な括弧文字列」として保持し、vに対して再帰操作を実行する.
2つの文字列u,vを再び区切る.
u = "))(("
v = "()"
uは「有効な括弧文字列」ではないため、次のように新しい文字列を作成します.
ステップ1からvの再帰操作が開始された場合は「()」を返します.
uの前後文字を削除し、残りの文字のカッコ方向を反転すると、その文字は「()」になります.
したがって、生成された文字列は「(」+「()」+「()」+「()」であり、最終的には「()()」を返します.
返された文字列が最初に保持されていた文字列に接続されている場合は、"()"()"+"(()()"="()()()()()()()")になります.

👨‍💻コードと解釈

function solution(w) {
  if (w === "") return ""; // 빈 문자열인 경우, 빈 문자열 반환
  let u, v;
  let cnt = 0;

  for (let i = 0; i < w.length; i++) {
    w[i] === "(" ? cnt++ : cnt--;
    // 균형잡힌 괄호 문자열로 더이상 분리 될 수 없는 인덱스 찾기
    if (cnt === 0) {
      // u, v로 분리
      u = w.slice(0, i + 1);
      v = w.slice(i + 1);
      break;
    }
  }

  if (!isPerfect(u)) {
    // u가 올바른 괄호 문자열이 아니므로 4 과정 수행
    let str = "";
    str += `(${solution(v)})`; // 4-1, 4-2, 4-3과정 한번에 수행
    for (let i = 1; i < u.length - 1; i++) {
      // 첫번째, 마지막 문자 생략 후 뒤집에서 붙이기
      u[i] === "(" ? (str += ")") : (str += "(");
    }
    return str; // 반환
  }

  return u + solution(v); // u가 올바른 문자열일 때 3 과정 수행
}

function isPerfect(str) {
  // 올바른 괄호 문자열을 판단하는 함수
  if (str === "" || str[0] === ")" || str[str.length - 1] === "(") return false;
  let cnt = 0;
  for (let i = 0; i < str.length; i++) {
    str[i] === "(" ? cnt++ : cnt--;
  }
  return cnt === 0 ? true : false;
}

👨‍💻その他のプールコード

function reverse(str) {
  return str.slice(1, str.length - 1).split("").map((c) => (c === "(" ? ")" : "(")).join("");
}

function solution(p) {
  if (p.length < 1) return "";

  let balance = 0;
  let pivot = 0;
  do { balance += p[pivot++] === "(" ? 1 : -1 } while (balance !== 0);

  const u = p.slice(0, pivot);
  const v = solution(p.slice(pivot, p.length));

  if (u[0] === "(" && u[u.length - 1] == ")") return u + v;
  else return "(" + v + ")" + reverse(u);
}

😃ポスト
これは逐次漸進的な問題である.