BOJ 2800 괄호제거 JAVA

문제 링크: https://www.acmicpc.net/problem/2800

 

🌟 사용한 알고리즘 및 자료구조

- 비트 마스킹 (백트래킹 할 때 사용)

- 스택 (괄호 쌍 구할 때)

- 우선순위큐 (문자열 사전 순 출력)

- 맵 (문자열 중복 검사)

 

🌟  만약 15% 에서 틀린다?

다음 반례 참고 (문자열 중복 검사를 해야함) 

https://www.acmicpc.net/board/view/129131

 

 

🌟 코드 (JAVA) 

1. 괄호의 갯수 파악 필요 (문제에 주어진 수식은 괄호가 올바르단 명제가 있기 때문에 따로 검사 X)

- 괄호 쌍 확인 방법 -> [스택] 사용

- 괄호 인덱스 보관 -> 배열 사용 

 

2. 괄호의 갯수는 10개가 최대임이 문제에 나와있기 때문에 백트래킹 문제 없음. 

- 괄호의 갯수 만큼 백트래킹 돌림 

- 자세한건 코드 참조

 

3. 우선순위큐에 보관한 문자열 뽑음. 이때 중복이 있으면 안됨. 

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

// 괄호 제거 비트마스킹, 백트래킹, 스택
public class B_2800 {
    String s;

    void solve() {

        //1. 괄호의 쌍을 보관하는 인덱스 저장소 생성.
        List<int[]> list = new ArrayList<>();

        //2. 괄호 위치 확인
        Stack<Integer> stack = new Stack();
        for (int i = 0; i< s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.add(i);
            } else if (c == ')') {
                int stIdx = stack.pop();
                list.add(new int[] {stIdx, i});
            }
        }

        // 3. 괄호의 쌍 갯수 확인
        int size = list.size();

        // 4. 괄호의 쌍만큼 비트마스킹 돌림
        // 4.1 수식 보관할 우선순위큐 생성
        PriorityQueue<String> pq = new PriorityQueue<>();
        Map<String, Integer> vis = new HashMap<>();


        for (int bit = 1; bit < (1 << size); bit++) {

            boolean[] no = new boolean[s.length()];
            for (int i = 0; i < size; i++) {
                if ((bit & (1 << i)) > 0) {
                    int[] idx = list.get(i);
                    int st = idx[0], en = idx[1];
                    no[st] = true;
                    no[en] = true;
                }
            }
            
            // 4.2 만들어진 수식 보관 (중복 검사 필요)
            String tmp = "";
            for (int i = 0; i < s.length(); i++) {
                if (!no[i]) tmp += s.charAt(i);
            }
            if (!vis.containsKey(tmp)) {
                pq.add(tmp);
                vis.put(tmp, 1);
            }

        }

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }

    }

    void init() {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            s = br.readLine();
            solve();
        } catch (Exception e) {}
    }
    public static void main(String[] args) {
        B_2800 b = new B_2800();
        b.init();
    }
}