[백준]#2800 괄호 제거

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(23, ((2+3)4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(22)+2)에서 괄호를 제거하면, (2+22+2), 2+(22)+2, 2+22+2를 만들 수 있다. 하지만, (2+22)+2와 2+(22+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다.

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

예제 입력 1

(0/(0))

예제 출력 1

(0/0)
0/(0)
0/0

예제 입력 2

(2+(2*2)+2)

예제 출력 2

(2+2*2+2)
2+(2*2)+2
2+2*2+2

예제 입력 3

(1+(2*(3+4)))

예제 출력 3

(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4

풀이

이 문제는 스택을 이용해서 여는 괄호와 닫히는 괄호 쌍을 구하고 괄호쌍을 토대로 깊이 우선 탐색을 통해 순서있는 조합을 통해 답을 구했다.

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

public class Main {
    static ArrayList<Pair> list;    //괄호쌍 저장 리스트
    static StringBuilder sb;    
    static TreeSet<String> res;     //괄호 삭제된 각 문자열 정렬 및 저장

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        list = new ArrayList<>();
        res = new TreeSet<>();
        Stack<Integer> stack = new Stack<>();     //괄호 쌍 구하기 위한 스택

        for(int i=0; i<str.length(); i++) {
            char c = str.charAt(i);

            if(c=='(')
                stack.push(i);          //여는 괄호면 스택에 인덱스 넣음

            else if(c==')') {         //닫는 괄호 나오면 가까운 여는 괄호 인덱스와 함께 Pair쌍 생성
                list.add(new Pair(stack.pop(), i));
            }
        }

        dfs(str, 0);

        for(String ans : res)
            System.out.println(ans);
    }

    public static void dfs(String str, int idx) {
        if(idx>=list.size()) return;

        for(int i=idx; i<list.size(); i++) {
           Pair temp = list.get(i);

           sb = new StringBuilder(str);
           sb.replace(temp.open, temp.open+1, " ");       //괄호 삭제 쉽게 괄호를 공백으로 치환해서 문자열 길이 유지
           sb.replace(temp.close, temp.close+1, " ");
           res.add(sb.toString().replaceAll(" ", ""));    //셋에 넣을 때는 공백삭제 후 추가
           dfs(sb.toString(), i+1);
           sb.replace(temp.open, temp.open+1, "(");
           sb.replace(temp.close, temp.close+1, ")");
        }
    }

    public static class Pair {        //괄호쌍 저장 위한 클래스 구현
        int open;
        int close;

        public Pair(int open, int close) {
            this.open = open;
            this.close = close;
        }
    }
}