[BOJ] 2800 - 괄호 제거 JAVA

www.acmicpc.net/problem/2800

2800번: 괄호 제거

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

예제 입력 1

(0/(0))

예제 출력 1

(0/0)

0/(0)

0/0

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = null;
    static StringBuilder sb = null;
    static Stack<Integer> stk = null;
    static Set<String> set = null;

    static String str = null;
    static int[] pair = null;  // 괄호 쌍 서로의 인덱스 저장하는 배열
    static boolean[] check = null;  // 나와 쌍을 맺는 괄호 지울 것인지

    public static void dfs(int deptNow, int dept) {
        if(deptNow == dept) {
            set.add(sb.toString());
            return;
        }

        char ch = str.charAt(deptNow);
        if(ch == '(') {
            check[deptNow] = true;
            dfs(deptNow+1, dept);  // 해당 쌍의 괄호를 지우는 경우
            check[deptNow] = false;
        }

        if(ch == ')' && check[pair[deptNow]]) {  // 나와 쌍인 '('가 지워져있는지 체크
            check[deptNow] = true;  // 사실 이어져있는 괄호 쌍은 하나뿐이라 여기서 굳이 check 건드릴 필요는 없긴 함
            dfs(deptNow+1, dept);
            check[deptNow] = false;
        }else {  // 괄호 안 지우는 경우 or 숫자일 경우
            sb.append(ch);
            dfs(deptNow+1, dept);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        stk = new Stack<>();
        set = new HashSet<>();

        str = br.readLine();
        pair = new int[str.length()];
        check = new boolean[str.length()];

        int len = str.length();
        for(int i = 0; i < len; i++) {  // 자신과 쌍을 이루는 괄호의 인덱스를 갖도록 함
            char ch = str.charAt(i);
            if(ch == '(') {
                stk.push(i);
            }else if(ch == ')') {
                pair[i] = stk.peek();  // 1, 3 인덱스에 '(', ')' 쌍이 위치할 경우
                pair[stk.peek()] = i;  // pair[1] = 3, pair[3] = 1 이렇게
                stk.pop();
            }
        }

        dfs(0, str.length());
        set.remove(str);  // 괄호를 하나도 삭제하지 않은 경우는 제외
        ArrayList<String> list = new ArrayList<>(set);
        Collections.sort(list);
        for (String s : list) {
            sb.append(s).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

아직 스택 사용이 익숙하지 않은 듯 하다.

 

구현에서 애를 많이 먹었다.

 

1. int[] pair을 사용해서 괄호들에 대하여 자신과 쌍을 이루는 괄호의 인덱스를 기억하도록 한다.

2. 백트래킹을 통해 괄호쌍을 지우는 경우와 지우지 않는 경우 모두를 수행한다.

 

사전순 출력 조건을 위해 정렬을 하려고 ArrayList를 사용했는데 이것 때문에 22%에서 틀렸습니다가 떴다.

 

반례를 찾아서 넣어보니 똑같은 정답이 중복 출력되는 문제가 있었다.

 

괄호가 여럿이 겹쳐있는 경우에는 다른 괄호쌍을 지우더라도 결과가 같아질 수 있기 때문에 중복 정답이 담기게 된다.

(ex : (((3)))의 경우에서 첫번째, 두번째, 세번째 괄호쌍을 지운 각각의 경우는 모두 ((3))으로 같다)

 

정답 케이스를 Set에 담고 그 Set으로 ArrayList를 만들어서 정렬하는 방식으로 문제를 해결했다.