[BOJ] 2800번 괄호 제거 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.TreeSet;

public class Main {

    static ArrayList<Pos> posList = new ArrayList<>();
    static TreeSet<String> set = new TreeSet<>();

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

        String input = br.readLine();
        Stack<Integer> stack = new Stack<>();


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

            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                posList.add(new Pos(stack.pop(), i));
            }
        }


        dfs(0, posList.size(), input);
        set.remove(input);

        StringBuilder sb =  new StringBuilder();
        for (String s : set) {
            sb.append(s).append("\n");
        }

        System.out.println(sb);
    }

    private static void dfs(int depth, int n, String s) {
        // 공백 제거 후 Set 에 추가
        if (depth == n) {
            set.add(s.replaceAll(" ", ""));
            return;
        }

        Pos pos = posList.get(depth);
        StringBuilder sb = new StringBuilder(s);
        sb.setCharAt(pos.start, ' ');
        sb.setCharAt(pos.end, ' ');

        // 제거하는 경우
        dfs(depth + 1, n, sb.toString());
        // 제거하지 않는 경우
        dfs(depth + 1, n, s);
    }

    static class Pos {
        int start;
        int end;

        public Pos(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

📄 해설

접근

• 스택, DFS, TreeSet 을 사용해야 해결할 수 있는 문제이다.
• 이 문제 또한 접근이 상당히 어려웠고, TreeSet 을 사용한 적이 없어서 결국 다른 사람의 풀이를 보고 풀었다.
• 또한 괄호의 시작과 끝의 위치를 나타낼 클래스 Pos 를 구현해야한다.
• 해당 괄호를 제거하는 경우와 그렇지 않은 경우를 위해 DFS 알고리즘을 사용해야한다.
• 사전 순으로 출력해야한다는 조건을 맞추기 위해 자동으로 정렬되는 TreeSet 을 사용한다.

과정

• 정수형 스택 하나와 TreeSet 객체 하나, Pos 리스트를 사용한다.
• 입력 문자열에서 여는 괄호를 만난 경우는 스택에 현재 인덱스의 번호를 넣고, 닫는 괄호를 만난 경우 스택에서 괄호의 시작 위치를 꺼내어 Pos 객체를 새로 생성하고, 리스트에 추가한다.
• DFS 알고리즘을 수행해서 결과 문자열들을 담을 TreeSet 을 만든다.
• depth 가 괄호의 개수인 n 과 같은 경우, 공백을 제거하고 TreeSet 에 추가한다.
• 그렇지 않은 경우는 depth 인덱스에 위치한 괄호의 위치 정보를 꺼내서 해당 괄호를 제거한 문자열을 하나 만들고, 괄호를 제거하는 경우와 그렇지 않은 경우로 재귀 호출을 진행한다.
• DFS 알고리즘 수행이 끝난 후, TreeSet에서 입력 받았던 문자열을 제거한 다음, TreeSet 에 존재하는 모든 문자열을 출력한다.