[백준] 괄호 제거 #2800

설명

오랜만에 골드 문제를 푸니 어려웠다..
재귀를 통해 dfs를 구현하여 문제를 해결했다.
괄호쌍의 인덱스를 들고 있고, 그 괄호쌍을 제거할지 말지를 결정하여
result에 담아줬다.
((0))과 같은 input이 주어지면 첫 번재 괄호쌍을 제거하나 두 번째 괄호쌍을 제거하나 결과가 같기 때문에 result의 자료형을 Set으로 두어 중복을 제거해주고, 결과를 출력했다.

Node.js 풀이

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

const solution = (str) => {
  const stack = [];
  const brackets = [];
  const result = new Set();
  const selected = new Array(str.length).fill(true);

  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') stack.push(i);
    else if (str[i] === ')') brackets.push([stack.pop(), i]);
  }

  const dfs = (idx, cnt) => {
    if (idx === brackets.length) {
      if (cnt > 0) {
        let temp = '';
        for (let i = 0; i < str.length; i++) {
          if (selected[i]) temp += str[i];
        }
        result.add(temp);
      }
      return;
    }
    dfs(idx + 1, cnt);
    selected[brackets[idx][0]] = false;
    selected[brackets[idx][1]] = false;
    dfs(idx + 1, cnt + 1);
    selected[brackets[idx][0]] = true;
    selected[brackets[idx][1]] = true;
  };
  dfs(0, 0);
  return [...result].sort().reduce((acc, cur) => acc + cur + '\n', '');
};

console.log(solution(input));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

string str;
bool selected[203];
vector<pair<int, int>> brackets;
set<string> result_set;

void dfs(int idx, int cnt) {
    if (idx == brackets.size()) {
        if (cnt > 0) {
            string tmp = "";
            for (int i=0; i<str.length(); i++) {
                if (selected[i]) tmp += str[i];
            }
            result_set.insert(tmp);
        }
        return;
    }
    dfs(idx + 1, cnt);
    selected[brackets[idx].first] = false;
    selected[brackets[idx].second] = false;
    dfs(idx + 1, cnt + 1);
    selected[brackets[idx].first] = true;
    selected[brackets[idx].second] = true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    stack<int> S;
    cin >> str;
    for (int i=0; i<str.length(); i++) {
        selected[i] = true;
        if (str[i] == '(') S.push(i);
        else if (str[i] == ')') {
            brackets.push_back({ S.top(), i });
            S.pop();
        }
    }
    
    dfs(0, 0);
    for (auto result : result_set) cout << result << '\n';
    
    return 0;
}