[Algo] 백준 2800 괄호 제거 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/2800

메모리 : 26332KB

시간 : 280ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.TreeSet;

public class Main {
    static int[] bracket;
    static boolean[] check;
    static int idx, cnt;
    static TreeSet<String> anslist = new TreeSet<>();
    static String str;

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        bracket = new int[str.length()];
        cnt = 0;
        idx = 1;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                cnt++;
                bracket[i] = idx;
                stack.add(idx++);
            } else if (str.charAt(i) == ')') {
                bracket[i] = stack.pop();
            }
        }
        check = new boolean[cnt + 1];
        dfs(1);
        anslist.remove(str);
        StringBuilder sb = new StringBuilder();
        for (String s : anslist) {
            sb.append(s).append("\n");
        }
        System.out.println(sb);
    }

    private static void dfs(int idx) {
        if (idx > cnt + 1)
            return;

        String tmp = "";
        for (int i = 0; i < str.length(); i++) {
            if (bracket[i] != 0 && check[bracket[i]]) {
                continue;
            } else {
                tmp += str.charAt(i);
            }
        }
        anslist.add(tmp);
        for (int i = idx; i <= cnt; i++) {
            check[i] = true;
            dfs(i + 1);
            check[i] = false;
        }
    }
}

풀이

1. stack으로 괄호에 몇번째 괄호인지 번호를 메긴다.
   • 여는괄호 ( 에 시작번호 idx 를 할당해서 붙여주고 이를 스택에 넣는다. 이는 먼저 열린 괄호가 나중에 닫히는 성질을 이용하기 위해서이다.
   • 닫는괄호 ) 가 나오면 스택에서 가장 위에 있는 idx를 꺼내 붙여준다. 상기하였듯 최근에 열린 괄호가 가장 빨리 닫히기 때문이다.
2. 괄호의 개수로 조합을 만들어 어떤 괄호를 제거할 것인지 경우의 수를 계산한다.
   • 이때 제거하기로 한 괄호는 check 배열에 표시되고, 해당 괄호가 bracket에 표시된 그 번호인지 검사해준다.
3. 만든 문자열을 TreeSet에 넣거 중복제거+사전순정렬의 효과를 누린다.