[백준] 2800. 괄호 제거 - Java

🖇️ 문제 링크

2800번: 괄호 제거

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

 

---

💡 문제 분석

1. 괄호쌍의 인덱스를 리스트에 저장해놓습니다

2. 괄호쌍들의 집합으로 공집합을 제외하고 모든 부분집합을 생성합니다.

3. 생성한 부분집합에 따라, 괄호쌍들을 제거하고 결과 리스트에 저장합니다.

4. 사전순으로 정렬한 후 출력합니다

 

 

---

⌨️ 코드

import java.util.*;

public class Q2800 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        Deque<Integer> stk = new ArrayDeque<>();
        List<int[]> pair = new ArrayList<>();
        List<String> ret = new ArrayList<>();

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

            if(c == '(') {
                stk.push(i);
            } else if(c == ')') {
                int s = stk.pop();
                pair.add(new int[]{s, i});
            }
        }

        int len = pair.size();
        // 괄호 쌍의 개수의 부분집합만큼 괄호 삭제
        for(int i = 1; i < (1 << len); i++) {
            List<Integer> chk = new ArrayList<>();
            StringBuilder tmp = new StringBuilder(str);
            for(int j = 0; j < len; j++) {
                if((i & (1 << j)) != 0) {
                    chk.add(pair.get(j)[0]);
                    chk.add(pair.get(j)[1]);
                }
            }

            chk.sort(Comparator.reverseOrder());
            for(int n : chk)
                tmp.deleteCharAt(n);

            ret.add(tmp.toString());
        }

        ret.stream()
                .distinct()
                .sorted(Comparator.naturalOrder())
                .forEach(System.out::println);
    }
}

 

---

⏱️ 결과

 

 

 

Uploaded by Notion2Tistory v1.1.0