이번에 풀어본 문제는
백준 2800번 괄호 제거 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Pair
{
int left, right;
public Pair(int left, int right) {
this.left = left;
this.right = right;
}
}
public class Main {
static List<Pair> pairs;
static int pairCount;
static Set<String> set;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
Stack<Integer> stk = new Stack<>();
set = new TreeSet<>();
pairs = new ArrayList<>();
int inputSize = input.length();
for (int i = 0; i < inputSize; i++) {
char cur = input.charAt(i);
if (cur == '(') {
stk.add(i);
}
else if (cur == ')') {
pairs.add(new Pair(stk.pop(), i));
}
}
pairCount = pairs.size();
makeString(0, input+"");
// 입력값은 제거
set.remove(input);
StringBuilder answer = new StringBuilder();
for (String s : set) {
answer.append(s).append("\n");
}
System.out.print(answer);
}
static void makeString(int idx, String str) {
if (idx == pairCount) {
//공백 제거 후 set에 add
set.add(str.replaceAll(" ",""));
return;
}
// 현재 괄호를 제거
Pair pair = pairs.get(idx);
StringBuilder sb = new StringBuilder(str);
sb.setCharAt(pair.left,' ');
sb.setCharAt(pair.right, ' ');
makeString(idx + 1, sb.toString());
// 제거 안함
makeString(idx + 1, str);
}
}
괄호를 제거하여 만들 수 있는 모든 수식을 출력하는 문제입니다.
Stack으로 괄호 쌍을 모두 구해주고, 각 쌍들을 조합하여 만들 수 있는 모든 경우의 수를 구해주면 됩니다. 결괏값은 TreeSet에 담아 중복값을 제거함과 동시에 문제에 주어진 조건인 사전순으로 정렬되도록 할 수 있습니다. 괄호를 모두 제거하지 않을 경우도 포함되므로, 출력 이전에 입력값을 Set에서 지워주고, 나머지 식을 모두 출력하면 해결됩니다.
제 풀이에 확신이 들지 않아서 푸는 내내 고민이 많았는데, 끝나고 다른 풀이를 참고해보니 비슷한 해답이었네요..
앞으로는 틀리더라도 자신감있게 푸는 연습도 해야할 것 같습니다!