[백준 2800] 괄호 제거 (JAVA)

문제

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

풀이

스택을 통해 괄호를 짝지어주고 재귀를 통해 괄호를 표시할지 말지 결정 후 나온 식을 HashSet이나 TreeSet을 이용해 중복을 제거해줍니다. (HashSet 경우 정렬 후 출력해야합니다.)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static char[] input;
    static ArrayList<bracket> brackets = new ArrayList<>();
    static TreeSet<String> set = new TreeSet<>();
    static boolean[] visited;
    static boolean isFirst = true;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Stack<Integer> stack = new Stack<>();
        input = br.readLine().toCharArray();
        for (int i = 0; i < input.length; i++) {
            char c = input[i];
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                brackets.add(new bracket(stack.pop(), i));
            }
        }
        visited = new boolean[input.length];
        Arrays.fill(visited, true);
        find(0);

        for (String s : set) {
            sb.append(s).append('\n');
        }

        System.out.println(sb);
        br.close();
    }

    public static void find(int depth) {

        if (depth == brackets.size()) {
            if (isFirst) {
                isFirst = false;
            } else {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < input.length; i++) {
                    if (visited[i]) {
                        sb.append(input[i]);
                    }
                }
                set.add(sb.toString());
            }
            return;
        }

        bracket bracket = brackets.get(depth);
        visited[bracket.start] = true;
        visited[bracket.end] = true;
        find(depth + 1);

        visited[bracket.start] = false;
        visited[bracket.end] = false;
        find(depth + 1);
    }

    public static class bracket {
        int start, end;

        public bracket(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}