[백준/JS] 2800 괄호제거

문제링크

2800번: 괄호 제거

 

문제풀이

제게 너무 힘든문제였습니다.

참고한 블로그입니다.

조눅's 괴발개발

[백준] 괄호 제거

인간디버거의로그찍기

BOJ - 괄호 제거 2800번 (python)

 

주요한 아이디어는

• 괄호의 인덱스를 넣는다.
• 조합을 통해 괄호쌍을 1개부터 총 괄호의 갯수까지 뽑습니다. 즉 괄호가 3개있다면 괄호1개 , 괄호2개 , 괄호3개일 경우를 조합으로 구하는 것입니다.
  • 괄호를 제거할때 처음에는 slice 를 해서 구하려고 했는데, 괄호쌍이 한개도 아니고 6개 정도되어버리면 slice를 6번 사용했어야했는데 말이 안되었습니다.
  • 따라서 괄호쌍의 index를 flat으로 1차원배열로 모아서 includes 를 사용하여 해당 index 가 포함되는지 안되는지 여부에 따라 result에 저장하는 방식을 사용했습니다. 
• set을 통해 중복을 제거한다.
• sort 한다.

const fs = require("fs");

BOJkey = 1;

let input = fs
  .readFileSync(BOJkey ? "./자바스크립트로/2800/input.txt" : "./dev/stdin")
  .toString()
  .trim();

const combination = (arr, selectNum) => {
  const result = [];
  if (selectNum == 1) return arr.map((v) => [v]);
  arr.forEach((v, index, arr) => {
    const fixed = v;
    const restArr = arr.slice(index + 1);
    const combinationArr = combination(restArr, selectNum - 1);
    const combineFix = combinationArr.map((v) => [fixed, ...v]);
    result.push(...combineFix);
  });
  return result;
};

let stack = [];
let temp = 0;
let candidate = [];
//괄호의 인덱스를 넣는다.
for (let i = 0; i < input.length; i++) {
  if (input[i] == "(") {
    stack.push(i);
  } else if (input[i] == ")") {
    temp = stack.pop();
    candidate.push([temp, i]);
  }
}

let test = [];
let answer = [];
for (let j = 1; j <= candidate.length; j++) {
  // 조합을 통해 괄호쌍을 1개부터 총 괄호의 갯수까지 뽑습니다. 즉 괄호가 3개있다면 괄호1개 , 괄호2개 , 괄호3개일 경우를 조합으로 구하는 것입니다.
  asss = combination(candidate, j);
  for (let i = 0; i < asss.length; i++) {
    result = "";
    // 괄호쌍의 index를 flat으로 1차원배열로 모아서 includes 를 사용하여 해당 index 가 포함되는지 안되는지 여부에 따라 result에 저장하는 방식을 사용했습니다.
    test = asss[i].flat();
    for (let k = 0; k < input.length; k++) {
      if (!test.includes(k)) {
        result += input[k];
      }
    }
    answer.push(result);
  }
}
// set을 통해 중복을 제거한다. sort 한다.
let final = [...new Set(answer)].sort();
console.log(final.join("\n"));