[Gold IV] 괄호 제거 - 2800

문제 링크

성능 요약

메모리: 19808 KB, 시간: 240 ms

분류

자료 구조, 문자열, 브루트포스 알고리즘, 스택

제출 일자

2025년 5월 9일 09:44:20

문제 설명

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

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 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개이다.

출력

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

풀이

스택을 이용해 괄호가 맞물릴 때 괄호 쌍을 인덱스로 저장해놓고

해당 저장해둔 괄호 배열을 dfs로 돌려서 완전 탐색을 돌려도 정답이 나오긴 한다.

그러나, 비트마스킹으로 푸는 방법도 있다고 해서 비트 마스킹으로 풀이를 한 번 해봤다.

3가지로 만들 수 있는 조합을 2진수로 나타내면 어떻게 될까

0 0 0 -> 0

0 0 1 -> 1

0 1 0 -> 2

1 0 0 -> 4

0 1 1 -> 3

1 0 1 -> 5

1 1 0 -> 6

1 1 1 -> 7

0 ~ 7까지 숫자를 2진수로 표현한 것이 3가지 품목을 대상으로 만들 수 있는 모든 조합의 종류와 같다.

다만 숫자를 2진수로 표현해야

어떤 품목이 선택됐는지를 파악할 수 있기 때문에

0 0 1

0 1 0

1 0 0

세 가지 숫자를 돌아가며 비트 & 연산을 때려야한다.

& 연산을 했을 때 0이 아닌 값이 나온다면 해당 품목은

조합에 들어가도록 선택된 품목이라는 사실을 알 수 있다.

마지막으로 1 0 0과 & 1 1 1 연산을 했다고 하면

1 0 0 즉 4가 나왔을 것이다.

4가 나왔다면 2번째 품목이 선택됐다는 얘긴데,

이 말은 log2(4)와 같다.

이렇게 순서까지 찾아냈다면,

모든 조합을 수월하게 찾을 수 있을 것이다.

전체 코드

public class 괄호제거 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] a = br.readLine().toCharArray();

        Stack<Integer> stack = new Stack<>();
        List<Integer[]> gualho = new ArrayList<>();
        Set<String> last = new TreeSet<>();

        for (int i = 0; i < a.length; i++) {
            if (a[i] == '(') {
                stack.push(i);
            } else if (a[i] == ')') {
                gualho.add(new Integer[]{stack.pop(), i});
            }
        }

        int length = (int) Math.pow(2, gualho.size()) - 1;
        for (int i = 1; i <= length; i++) {
            List<Integer> index = new ArrayList<>();
            for (int j = 1; j <= (int) Math.pow(2, gualho.size() - 1); j <<= 1) {
                if ((i & j) != 0) {
                    index.add(log2(j));
                }
            }
            char[] copyArr = a.clone();
            for (Integer integer : index) {
                for (int k = 0; k < a.length; k++) {
                    if (k == gualho.get(integer)[0] || k == gualho.get(integer)[1]) {
                        copyArr[k] = 'a';
                    }
                }
            }
            String result = String.valueOf(copyArr).replace("a", "");
            last.add(result);
        }
        for (String s : last) {
            System.out.println( s);
        }
    }

    public static int log2(int x) {
        return (int) (Math.log(x) / Math.log(2));
    }
}