백준 2800 (괄호 제거) - java

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

2800번: 괄호 제거

 

문제

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

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

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

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

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

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

 

유형 : 스택

 

접근 방식

• 괄호의 '(' 가 있을 때 가장 먼저 만나는 ')' 가 하나의 쌍이다. 즉 스택의 성질을 이용하면 된다.
• 순회를 통해 서로 쌍이 되는 괄호를 따로 저장한다. (최대 10개)
  • 해당 쌍의 부분 집합을 구한다. ( 1개의 쌍만 제거 .. 2개의 쌍 제거 .. 3개의 쌍 제거 ...) -> 공집합 제거 필요
• 주의할 점은 제거된 수식이 중복될 수 있다는 점이다. 그렇기 때문에 만들어진 결과쌍을 HashSet에 저장한다.
• 그리고 정렬하여 출력

전체 코드

package Implementation_BruteForce;

import java.io.*;
import java.util.*;
/*
((0/(0)))
((0/0))
(0/(0))
(0/0)
0/(0)
0/0
* */
public class BOJ_2800_괄호제거 {
    static StringBuilder sb = new StringBuilder();
    static boolean[] isSelected;
    static String line;
    static ArrayList<Garo> list;
    static char[] tmpArr;
    static HashSet<String> set = new HashSet<>();

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

        line = br.readLine();

        tmpArr = line.toCharArray();
        int len = tmpArr.length;

        Stack<Integer> stack = new Stack<>();
        list = new ArrayList<>();

        for(int i=0; i< len;i++){
            if(tmpArr[i] == '('){
                stack.push(i);
            }else if(tmpArr[i] == ')'){
                int sIdx = stack.pop();
                int eIdx = i;

                list.add(new Garo(sIdx,eIdx));
            }
        }

        int listSize = list.size();
        isSelected = new boolean[listSize];

        subSet(0,listSize,0);

        ArrayList<String> result = new ArrayList<>(set);

        Collections.sort(result,(x,y) -> x.compareTo(y));

        sb = new StringBuilder();
        for(String cur : result){
            sb.append(cur+"\n");
        }
        System.out.print(sb);
        br.close();
    }
    static void make(int N){
        sb = new StringBuilder();
        boolean[] tmpV = new boolean[tmpArr.length];

        for(int i=0;i<N;i++){
            if(isSelected[i]){
                tmpV[list.get(i).sIdx] = true;
                tmpV[list.get(i).eIdx] = true;
            }
        }

        for(int i=0,size = tmpV.length; i < size; i++){
            if(!tmpV[i]) sb.append(tmpArr[i]);
        }

        set.add(sb.toString());
    }
    static void subSet(int idx,int N,int count){

        if(idx == N){

            if(count == 0)
                return;

            make(N);
            return;
        }

        isSelected[idx] = true;
        subSet(idx+1,N,count + 1);
        isSelected[idx] = false;
        subSet(idx+1,N,count);
    }

}
class Garo{
    int sIdx;
    int eIdx;

    Garo(int sIdx,int eIdx){
        this.sIdx = sIdx;
        this.eIdx = eIdx;
    }
}