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