[백준] 2800 괄호 제거 java

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

public class DeleteBracket {
    static BufferedReader br;
    static StringBuilder sb;
    static Stack<Integer> s;
    static List<brckXy> list;
    static int brckNum;
    static List<String> res;
    static HashSet<String> dup;

    public static void main(String[] args) throws IOException{
        input();
        searchBrck();
        solve(0, "");
        Collections.sort(res);
        for(int i = 0; i < res.size(); i++) {
            if(!dup.contains(res.get(i))) {
                dup.add(res.get(i));
                System.out.println(res.get(i));
            }
        }
    }

    static void input() throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder(br.readLine());
        list = new ArrayList<>();
        s = new Stack<>();
        res = new ArrayList<>();
        dup = new HashSet<>();
    }

    /*
    @param r 현재 위치
    @param idx 삭제 할 list 인덱스 문자열로 저장
     */
    static void solve(int r, String idx) {
        if(r== brckNum && idx.equals("")) return;
        if(r == brckNum) {
            HashSet<Integer> set = new HashSet<>();
            for(int i = 0; i < idx.length(); i++) {
                //조합으로 뽑은 괄호 위치 인덱스를 담은 리스트를 하나씩 꺼내서 삭제
               brckXy point = list.get(idx.charAt(i)-'0');
               set.add(point.l);
               set.add(point.r);
            }
            StringBuilder ans = new StringBuilder();
            for(int i = 0; i < sb.length(); i++) {
                if(!set.contains(i)) {
                    ans.append(sb.charAt(i));
                }
            }
            res.add(ans.toString());
            return;
        }

        solve(r+1, idx+r);
        solve(r+1, idx);
    }

    static void searchBrck() {
        for(int i = 0; i < sb.length(); i++) {
            if(sb.charAt(i) == '(') {
                s.push(i);
            }
            if(sb.charAt(i) == ')') {
                int tmp = s.pop();
                list.add(new brckXy(tmp, i));
            }
        }
        brckNum = list.size();
    }
}

class brckXy {
    int l;
    int r;
    brckXy(int l, int r) {
        this.l = l;
        this.r = r;

    }
}

스택과 조합을 사용한 문제였다.

 

1. 스택을 이용해 괄호 쌍들의 위치를 저장한다. ( searchBrck() )

 

2. 조합 알고리즘을 이용하여 선택된 괄호의 위치를 이용하여 괄호를 제거한다.

 

3. 출력할 리스트에 괄호가 제거된 상태의 문자열을 저장한다.

 

4. 예외케이스로 공집합의 경우 괄호를 제거하지 않은 경우도 포함되기 때문에 예외로 빼준다.

 

5. 사전순으로 정렬한다.

 

6. 중복이 나오지 않게 제거 후 출력한다.