[백준] 괄호 제거 - 2800 JAVA

1. 문제

 

 

2. 접근

단순히 괄호 찾아서 지우는 문제인 줄 알았는데 괄호 쌍의 조합을 구해야 하는 문제였다. 

 

처음엔 스택만 이용하다가 괄호가 2개 이상 동시에 지워져야 한다는 것을 깨닫고 Set을 이용하여 괄호의 쌍 인덱스를 저장했었다. 하지만 구현이 계속 어려워져서 원점으로 돌아가서 다시 생각했다.

 

중간에 문제를 잘못 이해한 것을 깨달았으면 구현하고 있는 것을 계속 붙잡고 있을게 아니라 처음부터 다시 생각하는게 오히려 빠른 것 같다. 그냥 다시 생각하자.

 

처음부터 다시 생각한 결과, 괄호의 쌍들을 구해서 조합으로 뽑는 것으로 결정했다. 괄호의 쌍은 스택을 이용해서 구하고 요소 하나로 저장한다. 그 후 백트랙킹으로 괄호의 쌍을 1개부터 10개까지 선택한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;
import java.util.TreeSet;


class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static String origin;
    public static TreeSet<String> result;

    public static void main(String[] args) throws IOException {

        origin = br.readLine();
        result = new TreeSet<>();
        Stack<Integer> stack = new Stack<>();
        List<Pair> pairs = new ArrayList<>();

        // 괄호 쌍 찾기
        for(int i=0; i< origin.length(); i++){
            char cur = origin.charAt(i);

            if(cur == '('){
                stack.add(i);
            }
            else if(cur == ')'){
                pairs.add(new Pair(i, stack.pop()));
            }
        }

        for(int i=1; i<=10; i++){
            select(pairs, 0, 0, i, new HashSet<>());
        }

        for(String str: result){
            bw.write(str+"\n");
        }
        bw.flush();
    }

    // 선택하기
    private static void select(List<Pair> pairs, int idx, int depth, int k, HashSet<Integer> set){
        if(depth == k){
            result.add(extractStr(set));
            return;
        }

        int size = pairs.size();
        for(int i=idx; i<size; i++){
            int idx1 = pairs.get(i).idx1;
            int idx2 = pairs.get(i).idx2;
            set.add(idx1);
            set.add(idx2);

            select(pairs, i+1, depth+1, k, set);

            set.remove(idx1);
            set.remove(idx2);
        }
    }


    public static String extractStr(HashSet<Integer> set){
        char [] chars = new char[origin.length()-set.size()];
        int idx = 0;

        for(int i=0; i<origin.length(); i++){
            if(set.contains(i)){
                continue;
            }
            chars[idx++] = origin.charAt(i);
        }
        return new String(chars);
    }
}

class Pair{
    int idx1;
    int idx2;

    public Pair(int idx1, int idx2) {
        this.idx1 = idx1;
        this.idx2 = idx2;
    }
}

 

 

4. 개선 점

1. 조합 문자열 결과의 중복

구현 후 제출했는데 틀렸다고 떠서 이유를 찾아보니 중복 요소가 포함되어 출력되고 있었다. 분명 리스트의 요소를 선택할 때 선택한 것 다음부터 뽑는데 왜 중복이 발생하나 했는데 (((1))) 처럼 피연산자 하나에 여려 겹의 괄호가 있으면 중복으로 처리된 것이었다.

 

어떻게 중복을 거를까 하다가 제일 만만한 TreeSet을 사용했다.

 

2. char[] -> String

chars.toString() 를 했는데 print 결과가 객체의 주소가 출력되었다. 제일 좋은 방법은 `새 String` 을 만드는 것 같다.

char [] chars = new char[origin.length()-set.size()];
return new String(chars);

 

혹은 `StringBuilder`를 사용한다.

StringBuilder sb = new StringBuilder();
			for(int i=0; i<str.length; i++) {
				if(!check[i]) {
					sb.append(str[i]);
				} else f = true;
			}
			if(f) {
				result.add(sb.toString());

 

3. set -> boolean[]

뽑혔는지 바로 확인하기 위해서 set을 사용했는데 그냥 boolean 배열을 사용하는 것이 메모리도, 성능면에서도 좋은 것 같다.