[백준] 2800: 괄호 제거 - JAVA

in Algorithm on 자료 구조

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

풀이

브루트포스 문제.

괄호의 쌍을 매칭하여 출력하거나 출력 안 하거나 하면 되는 문제였다.

서로의 짝을 매칭 시킬 방법으로 여는 괄호가 나오면 스택에 넣고,

닫는 괄호가 나오면 스택의 제일 위에 있는 괄호와 짝을 맺는다.

서로의 짝의 번호를 배열에 저장했다.

짝을 모두 저장한 후 dfs 탐색을 통해 해당 괄호를 boolean 배열에 true, false로 체크하여

출력할지 안 할지를 저장했다.

중복 식을 제거하기 위해, 사전 순으로 정렬하기 위해 TreeSet을 이용했다.

메모리: 24900KB

시간: 280ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static char[] arr;
    static int[] pair;
    static TreeSet<String> set;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        arr = s.toCharArray();

        pair = new int[arr.length]; // 괄호의 서로의 짝을 저장할 배열
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                // 여는 괄호가 나오면 스택에 넣는다
                stack.push(i);
            } else if (arr[i] == ')') {
                // 닫는 괄호가 나오면 스택의 제일 위 번호를 짝으로 저장하고
                // 거꾸로도 짝으로 저장한다
                pair[i] = stack.peek();
                pair[stack.peek()] = i;
                stack.pop();
            }
        }

        set = new TreeSet<>();
        visit = new boolean[arr.length];
        dfs(0, arr.length);
        // 처음 주어진 식은 제외한다
        set.remove(s);
        
        StringBuilder sb = new StringBuilder();
        set.stream().forEach(ans -> sb.append(ans).append("\n"));

        System.out.println(sb);
    }

    private static void dfs(int idx, int len) {
        if (idx == len) {
            print();
            return;
        }

        if (arr[idx] == '(') {
            // 여는 괄호를 만나면 해당 괄호와 짝 괄호를 vist배열에 true처리한다
            visit[idx] = true;
            visit[pair[idx]] = true;
            dfs(idx + 1, len);

            // 해당 괄호 쌍의 visit배열을 다시 false처리한다
            visit[idx] = false;
            visit[pair[idx]] = false;
        }

        dfs(idx + 1, len);
    }

    private static void print() {
        String tmp = "";
        for (int i = 0; i < arr.length; i++) {
            // visit가 true인 괄호는 출력하지 않는다
            if (!visit[i]) {
                tmp += arr[i];
            }
        }
        set.add(tmp);
    }

}