이번에 풀어본 문제는
백준 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에서 지워주고, 나머지 식을 모두 출력하면 해결됩니다.

📜 후기

제 풀이에 확신이 들지 않아서 푸는 내내 고민이 많았는데, 끝나고 다른 풀이를 참고해보니 비슷한 해답이었네요..
앞으로는 틀리더라도 자신감있게 푸는 연습도 해야할 것 같습니다!