백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 2800 , 괄호 제거 [자료구조, 스택]

백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 2800 , 괄호 제거 [자료구조, 스택]

 

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


덧붙일 말 🏷️
조합을 사용하여도 시간 초과없이 잘 풀림.

 

 

 

문제 출처 🏠

https://www.acmicpc.net/problem/2800

2800번: 괄호 제거

 

 

 

 

요구사항 📋

주어지는 식을 제외하고 사용된 각 괄호 쌍의 유무로 만들어질 수 있는 모든 경우의 수를 출력하여라.

 

이때, 서로 다른 식을 사전순으로 출력하라.  => 중복 제거 하라는 뜻

 

 

 

 

해결 전략 📝

보자마자 조합이 생각났다. 근데, 시간초과가 나지 않을까 싶었는데 최대 괄호쌍이 많아야 10개라고 명시되어있기 때문에 시간초과가 발생하지 않을 것이라고 판단하여 조합을 사용하여 모든 괄호쌍을 확인하는 방법으로 풀이를 진행하였다.

 

https://pul8219.github.io/algorithm/algorithm-permutation-and-combination/

[알고리즘] 순열과 조합, 재귀함수 이해하기(JavaScript)

 

자바스크립트로 조합을 구현하는 법은 해당 블로그의 코드를 참고하였다.

 

 

 

조합을 사용하기 위해선, 우선 각 괄호의 쌍의 인덱스를 확인해야 한다.

 

 

해당 코드로 스텍에 저장하고 pop 하면서 각 쌍의 위치를 가진 인덱스를 묶어서 brackets 라는 배열에 저장시킨다.

 

이후 이 배열을 조합으로 돌려 경우의 수들이 나오면 이 경우의 수들에 맞게 포함되어있는 인덱스 위치에 있는 괄호만 활성화 시켜서 저장해주면 된다.

 

모든 경우의 수들을 저장해서 출력시키면 되는데

 

이때, 중복을 제거해서 사전순으로 출력해야함을 잊지말자.

 

 

 

 

 

반례 ⚠️

 

입력 :

(1+(2*(3+4)))

 

출력

(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4

 

 

 

 

 

 

정답 💯

 

const input = require("fs").readFileSync("/dev/stdin").toString().trim();

const exp = input;

function solution(exp) {
  let [idx, arr, brackets, store, answer] = [0, [], [], [], []];
  exp.split("").map((v) => {
    if (v === "(") arr.push(idx);
    else if (v === ")") {
      let s = arr.pop();
      brackets.push([s, idx]);
    }
    idx += 1;
  });

  const order = Array.from({ length: brackets.length }, (v, i) => i + 1);

  const getCombinations = (arr, cnt) => {
    const result = [];
    if (cnt === 1) return arr.map((v) => [v]);

    arr.forEach((fix, idx, origin) => {
      const rest = origin.slice(idx + 1);
      const combinations = getCombinations(rest, cnt - 1);
      const plus = combinations.map((combination) => [fix, ...combination]);
      result.push(...plus);
    });
    return result;
  };

  for (let i = 1; i <= brackets.length; i++)
    store = [...store, ...getCombinations(order, i)];

  store.map((orders) => {
    const bracket = [];
    orders.map((order) => {
      bracket.push(...brackets[order - 1]);
    });
    let tmp = "";
    for (let i = 0; i < exp.length; i++) {
      if (!bracket.includes(i)) tmp += exp[i];
    }
    answer.push(tmp);
  });
  answer = new Set(answer);
  return [...answer].sort();
}

solution(exp).map((v) => console.log(v));