[BOJ - JAVA] 2800 - 괄호 제거 (TreeSet, 백트래킹)

# 주소

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

2800번: 괄호 제거

# 문제

# 문제 해설 및 코드 리뷰

import java.lang.reflect.Array;
import java.util.*;
class Point{
    int start;
    int end;
    Point(int start, int end){
        this.start = start;
        this.end = end;
    }
}
class Main {
    static ArrayList<Point> list = new ArrayList<Point>();
    static char[] arr;
    static TreeSet<String> set = new TreeSet<>();
    static boolean[] visit;
    static boolean isFirst = true;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        arr = scan.next().toCharArray();
        for(int i = 0; i < arr.length; i++){
            char c = arr[i];
            if(c == '(')
                stack.push(i);
            else if(c == ')')
                list.add(new Point(stack.pop(), i));
        }
        visit = new boolean[arr.length];
        Arrays.fill(visit, true);
        dfs(0);
        for(String s : set)
            sb.append(s).append('\n');
        System.out.println(sb);
    }
    static void dfs(int depth){
        if(depth == list.size()){
            if(isFirst){
                isFirst = false;
            }else{
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < arr.length; i++){
                    if(visit[i])
                        sb.append(arr[i]);
                }
                set.add(sb.toString());
            }
            return;
        }
        Point now = list.get(depth);
        visit[now.start] = true;
        visit[now.end] = true;
        dfs(depth + 1);

        visit[now.start] = false;
        visit[now.end] = false;
        dfs(depth + 1);

    }
}

먼저 Point 클래스를 start, end변수로 가져올 것입니다.

괄호가 들어갈 인덱스들을 각각 ArrayList로 담을 것입니다.

class Point{
    int start;
    int end;
    Point(int start, int end){
        this.start = start;
        this.end = end;
    }
}

this.start, this.end로 가져오는 것은 BFS문을 잘 이해하고 계시면 익숙하실 것입니다.

이런 과정을 오버라이딩하여 Getter, Setter를 따로 만들지 않아도 구현할 수 있습니다.

static ArrayList<Point> list = new ArrayList<Point>();
static char[] arr;
static TreeSet<String> set = new TreeSet<>();
static boolean[] visit;
static boolean isFirst = true;

ArrayList와 char[]타입의 arr, TreeSet타입의 set을 사용할 것입니다.

TreeSet은 제 블로그에서 처음 다루네요.

보통 정렬, 검색할 때 사용하고 탐색하는데 있어서 시간이 꽤 걸리지만 이런식으로 값을 정렬하여 나타낼 때 주로 씁니다.

중복을 허용하지 않고 이진검색트리로 구현되는 특징을 가지고 있습니다.

https://blog.naver.com/wltjdrmsdl/222424404633

java 자료구조 - TreeSet

자세한건 여기서 참고해도 좋을 것 같아요

Comparable인터페이스로 구현이 가능한데, 블로그에서 다뤘던 PriorityQueue와 비슷하죠? 아래는 TreeMap의 설명

A NavigableSet implementation based on a TreeMap. 
The elements are ordered using their natural ordering, or by a Comparator provided at set creation time,
depending on which constructor is used.

아래는 PriorityQueue의 설명입니다.

An unbounded priority queue based on a priority heap. 
The elements of the priority queue are ordered according to their natural ordering,
or by a Comparator provided at queue construction time, 
depending on which constructor is used.

내용을 살펴보니 둘 다 Comparator 인터페이스에 의해 정렬을 할 수 있다고 하네요!

다만 PriorityQueue과 달리 사용 용도가 다르고 Comparator인터페이스를 쓰는 자료구조가 더 많고 속도 측면에서 Treeset이 굉장히 다른 자료구조에 비해 성능이 떨어진다고 얘기를 합니다.

아무래도 값을 넣고 인덱스를 찾는 것이 느리고 자료를 넣는다는 것에 의미가 큰 것이 Treeset이기 때문인 것 같아요.

이것보다 HashSet이나(이거도 set계열이라 느리지만) ArrayList가 훨씬 좋습니다만 중복을 제거할 수 있고 문제의 입력문의 문자열 길이가 길지 않기 때문에 TreeSet을 사용했습니다.

Scanner scan = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
arr = scan.next().toCharArray();
for(int i = 0; i < arr.length; i++){
    char c = arr[i];
    if(c == '(')
        stack.push(i);
    else if(c == ')')
        list.add(new Point(stack.pop(), i));
}

Scanner로 입력받았습니다.

StringBuilder도 무조건 사용해주셔야 합니다!

Stack도 사용할 것인데, 여기에 ( 또는 )의 위치값을 담겠습니다.

그리고 입력받은 것을 toCharArray()를 쓰면 array로 만들어주는데, arr에 모두 저장하겠습니다.

이후 for문을 이용하여 arr[i]의 값이 (면 stack에 i를 담고 )면 stack의 최상단 값을 제거한 값과 i를 모두 list에 담겠습니다.

이로서 괄호 세트가 3번 들어가면 list에는 총 6개의 값이 들어가겠지요.

dfs(0);
for(String s : set)
    sb.append(s).append('\n');
System.out.println(sb);

그리고 dfs(0)을 실행합니다.

이 0은 depth를 의미하는 파라미터입니다.

static void dfs(int depth){

백트래킹 기법으로 풀이할 것이기 때문에 depth가 list의 크기에 도달하면 sb를 담아야겠지요.

만약 괄호 세트가 3번있었다면 list의 크기는 6이므로 depth가 6이될 때 if문으로 따로 처리를 해야합니다.

따라서 아래의 구문을 통해 depth를 늘려주겠습니다.

Point now = list.get(depth);
visit[now.start] = true;
visit[now.end] = true;
dfs(depth + 1);

visit[now.start] = false;
visit[now.end] = false;
dfs(depth + 1);

now.start와 now.end를 true로, false로 분기시켜서 설정할 수 있습니다.

이를 통해 모든 경우의 수에 대해 visit을 true로, false로 선언할 수 있을 것입니다.

visit의 크기는 arr의 크기와 같습니다.

if(depth == list.size()){
    if(isFirst){
        isFirst = false;
    }else{
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++){
            if(visit[i])
                sb.append(arr[i]);
        }
        set.add(sb.toString());
    }
    return;
}

만약 depth가 list의 크기와 같아지면 isFirst를 true였다면 false로 바꿀 것입니다.

왜 이렇게 하냐면, isFirst로 구분하지 않으면 처음에 입력했던 구문 그대로 출력이 됩니다.

문제에서는 입력문 외의 연산문을 출력하도록 요구하고 있기 때문에 처음의 isFirst는 false로 바꾸고 이것이 false일 때에만 출력하도록 할 것입니다.

StringBuilder를 초기화하면서 sb에 담아야 하기 때문에 sb를 새로 선언하고 for문으로 visit이 true인 곳만 sb에 담겠습니다.

그리고 set에 sb를 toString()하여 추가하고 return합니다.

이렇게하면 set에는 정답이 쭉 담겨서 다시 위의 Main으로 돌아가는데요.

이 시점이 dfs가 끝난 시점이므로 이 다음엔 for문을 통해 set의 String s원소로 제일 처음 선언한 sb에 담습니다.

이 때 \n을 같이 append해야 줄바꿈이 일어나게 할 수 있습니다.

최종적으로 sb를 그대로 출력하면 정답이 됩니다.

감사합니다.