[백준/JAVA] 2800번: 괄호 제거

🔺 문제

2800번: 괄호 제거

 

 

 

🧩  해결 아이디어

• 문자열 + 스택 + 재귀

- 필요 자료구조

• (여는 괄호 위치, 닫는 괄호 위치) 저장 객체
• 괄호 위치 객체 저장 리스트
• 괄호 제거해서 나오는 식 저장할 TreeSet
• 괄호 지울지 말지 판단용 boolean 배열

- 여는 괄호인 경우, 스택에 시작 위치 인덱스를 넣는다.

- 닫는 괄호인 경우, (스택의 여는 괄호 인덱스, 현재 인덱스)를 넣는다.

- 재귀를 통해 괄호를 표시할지 말지 각 쌍들을 조합하여 만들 수 있는 모든 경우의 수를 구한다. (백트래킹)

- 결과는 TreeSet에 저장하여 중복을 없애고, 자동으로 사전 순 정렬하게 한다.

 

 

 

💥 유의사항

재귀를 돌려도 크기가 2^10이라 괜찮다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static char[] ch;
    
    static List<Pair> list = new ArrayList<>();
    static Set<String> result = new TreeSet<>();
    static boolean[] check; // 괄호 지울지 말지 판단하는 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ch = br.readLine().toCharArray();
        
        // 1. 괄호 쌍 구하기
        Stack<Integer> stack = new Stack<>();
        
        for(int i = 0 ; i < ch.length ; i++) {
            if(ch[i] == '(') {
                stack.push(i);
            }
            else if(ch[i] == ')') {
                list.add(new Pair(stack.pop(), i));
            }
        }
        
        // 2. 괄호 존재하는 모든 조합 구하기
        check = new boolean[ch.length];
        comb(0);
        
        // 출력하기
        Iterator<String> iter = result.iterator();  // set을 iterator 안에 담기
        while(iter.hasNext()) {
            System.out.println(iter.next());
        }
    }
    
    private static void comb(int depth) {
        if(depth == list.size()) {
            boolean b = false; // 괄호가 1개 이상 제거되었는지 나타내는 변수
            
            StringBuilder sb = new StringBuilder();
            for(int i = 0 ; i < ch.length ; i++) {
                if(!check[i]) {
                    sb.append(ch[i]);
                }
                else {
                    b = true;
                }
            }
            
            if(b) { // 최소 1개의 괄호가 제거된 경우, 결과 set에 저장
                result.add(sb.toString());
            }
            return;
        }
        
        // 현재 괄호 제거 안 함
        comb(depth + 1);
        
        // 현재 괄호 제거
        Pair now = list.get(depth);
        check[now.start] = true;
        check[now.end] = true;
        comb(depth + 1);
        check[now.start] = false;
        check[now.end] = false;
    }
}
 
class Pair {
    int start, end;
    
    public Pair(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
 

 

---

🔺 다른 풀이들

- 좀 깔끔해보여서! 나중에 읽기

괄호제거-2800번(java)

 

---

💬 느낀 점

쌍 사용할지 말지 구할 때 재귀 써야하는거 아니야? 했는데 진짜 재귀를 쓰는 것이었다고 한다.

비슷한 문제 보면서 감을 좀 익혀야겠다.....ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V	12.24	240225

 

 

 

(+231224 2회독, 240225 3회독)

개선된 점

- 재귀 쓸 생각을 하다,,

 

놓쳤던 점

- 재귀함수의 매개변수와 종료 조건 작성 부분

- 현재 위치의 괄호를 제거할지, 안 할지 코드로 작성하는 부분

// 현재 위치 괄호 제거 X
comb(depth + 1);

// 현재 위치 괄호 제거
int[] now = list.get(depth);

check[now[0]] = true;
check[now[1]] = true;
comb(depth + 1);

check[now[0]] = false;
check[now[1]] = false;

 

 

 

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static char[] ch;
    static Stack<Integer> st;
    
    static List<int[]> list = new ArrayList<>();    // (여는 괄호, 닫는 괄호 위치) 저장 리스트
    static boolean[] check;                         // 해당 위치 괄호 지울지 말지 판단용 배열
    
    static Set<String> result = new TreeSet<>();    // 결과 저장용 집합
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ch = br.readLine().toCharArray();
        
        st = new Stack<>();
        
        for(int i = 0 ; i < ch.length ; i++) {
            if(ch[i] == '(') {
                st.push(i);
            }
            else if(ch[i] == ')') {
                list.add(new int[] {st.pop(), i});
            }
        }
        
        // 괄호 쌍 제거
        check = new boolean[ch.length];
        comb(0);
        
        for(String s : result) {
            sb.append(s).append("\n");
        }
        System.out.println(sb);
    }
    
    private static void comb(int depth) {
        if(depth == list.size()) {
            StringBuilder tmp = new StringBuilder();
            boolean isRemoved = false;  // 괄호가 1개 이상 제거되었는지 나타냄
            
            for(int i = 0 ; i < ch.length ; i++) {
                if(!check[i]) {
                    tmp.append(ch[i]);
                }
                else {
                    isRemoved = true;
                }
            }
            
            if(isRemoved) {
                result.add(tmp.toString());
            }
            
            return;
        }
        
        // 현재 위치 괄호 제거 X
        comb(depth + 1);
        
        // 현재 위치 괄호 제거
        int[] now = list.get(depth);
        
        check[now[0]] = true;
        check[now[1]] = true;
        comb(depth + 1);
        
        check[now[0]] = false;
        check[now[1]] = false;        
    }
}
 

 

---

(참고)

✔ 풀이 참고

[BOJ] 백준 2800번 괄호 제거 (Java)

[백준] 2800. 괄호 제거 (자바 JAVA)

백준 2800 괄호 제거 (Java,자바)

 

[백준 2800] 괄호 제거 (JAVA)

 

 

✔ set 원소 출력 방법

자바 Set 사용법부터 출력까지