[Java] BaekJoon 2800. 괄호 제거(골드5) (부분집합) (DFS)

문제출처: https://www.acmicpc.net/problem/2800

2800번: 괄호 제거

 

문제이해

 

목표

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오. 괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.
ex) 
입력 : (0/(0))
출력:
(0/0)
0/(0)
0/0

 

풀이

 

1. 괄호쌍의 인덱스를 Stack을 이용하여 찾아서 저장한다.

2. 각 괄호쌍의 제거 or 제거안함을 이용하여 부분집합, 2의 n제곱 만큼의 경우의 수를 탐색한다.  

   => 괄호 제거는 visited[] =falase 로 한다.

  각 경우(재귀가 끝이나서 now==count 일때), visited를 체크하여 true인 것만 출력하면

  괄호를 제거하고 잘 출력 할 수 있다.

 

주의 

괄호를 제거할 때 visited로 하지 않고 StringBuilder로 만들어서 한 쌍, 한 쌍을 제거하면 인덱스가 밀려서 정확하게 괄호를 제거할 수 없다. 원본 String을 유지하면서 따로 visited를 만들어서 true인 것만 출력할 수 있도록 하자

 

소스코드

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

import static java.lang.System.in;

public class 괄호제거 {
    private static HashSet<String> answer;
    private static ArrayList<int[]> pairs;
    private static int count;
    private static boolean[] visited;
    private static char[] charArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        String s = br.readLine();
        pairs = new ArrayList<>();
        answer = new HashSet<>();
        visited = new boolean[s.length()];
        Arrays.fill(visited, true);

        // 괄호 쌍의 인덱스를 찾아서 저장
        charArr = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (charArr[i] == '(') {
                stack.add(i);
            } else if (charArr[i] == ')') {
                pairs.add(new int[]{stack.pop(), i});
            }
        }
        count = pairs.size(); // 부분집합으로 탐색해야한 괄호쌍의 size

        removeGaul(0); // 핵심 알고리즘

        // 정답 도출
        answer.remove(s);
        List<String> answerList = new ArrayList(answer);
        Collections.sort(answerList);
        StringBuilder sb = new StringBuilder();
        for (String s1 : answerList) {
            sb.append(s1).append("\n");
        }
        System.out.println(sb);
    }

    private static void removeGaul(int now) { // 부분집합
        if (now == count) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    sb.append(charArr[i]);
                }
            }
            answer.add(sb.toString());
            return;
        }

        // 부분집합
        // 괄호를 제거하지 않고 재귀
        int[] pair = pairs.get(now);
        visited[pair[0]] = true;
        visited[pair[1]] = true;
        removeGaul(now + 1);

        // 괄호를 제거하고 재귀
        visited[pair[0]] = false;
        visited[pair[1]] = false;
        removeGaul(now + 1);
    }
}