BOJ 2800 괄호 제거

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

문제

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

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

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

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

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

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

---

입력

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

---

출력

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

---

예제 입력 1

(0/(0))

예제 출력 1

(0/0)
0/(0)
0/0

예제 입력 2

(2+(2*2)+2)

예제 출력 2

(2+2*2+2)
2+(2*2)+2
2+2*2+2

… 이하 예제 생략

---

코드

이번 문제는 제거할 괄호 쌍을 고르는 조합 문제였다.

크게 어렵지 않은 문제였는데, 주의할 점은 출력 조건이 ‘서로 다른 식을 사전 순으로 출력한다.’ 는 것이다.

즉, 괄호를 제거한 식을 출력하기 전에 중복 검사를 해줘야 한다는 것이다.

풀이 과정은 다음과 같다.

1. 스택을 사용해서 각 괄호 쌍의 위치를 파악한다.
2. 제거할 괄호 쌍을 선택한다.
3. 처음에 주어진 식에서 괄호 쌍을 제거한다.
4. 괄호 쌍을 제거한 식의 중복 검사를 진행한다.
5. 사전 순으로 식들을 출력한다.

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

public class Main {

    static String initialExpression;
    static List<Point> brackets = new ArrayList<>();
    static PriorityQueue<String> expressions = new PriorityQueue<>();

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

        selectBrackets(0, 0);

        StringBuilder answer = new StringBuilder();
        expressions.poll(); // 맨 처음 주어진 수식은 출력 제외
        while (!expressions.isEmpty()) {
            answer.append(expressions.poll()).append('\n');
        }

        System.out.println(answer);
    }

    /**
     * 스택을 활용해서 짝이 되는 괄호 쌍의 인덱스를 알아내는 메소드
     */
    static void checkBrackets() {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < initialExpression.length(); i++) {
            if(initialExpression.charAt(i) == '(') {
                stack.push(i);
            } else if(initialExpression.charAt(i) == ')') {
                Point bracketPair = new Point(stack.pop(), i);
                brackets.add(bracketPair);
            }
        }
    }

    /**
     * 제거할 괄호 쌍을 고르는 메소드
     * 선택을 완료했을 경우, 선택한 괄호 쌍을 제거
     * @param checkBracket 제거 여부를 결정할 괄호
     * @param selected 제거할 괄호들을 표현한 비트마스크
     */
    static void selectBrackets(int checkBracket, int selected) {
        if(checkBracket == brackets.size()) {
            removeBrackets(selected);
            return;
        }

        selectBrackets(checkBracket + 1, selected);
        selectBrackets(checkBracket + 1, selected | 1 << checkBracket);
    }

    /**
     * 선택한 괄호 쌍을 제거하여 수식을 저장하는 메소드
     * @param selected 제거할 괄호들을 표현한 비트마스크
     */
    static void removeBrackets(int selected) {
        PriorityQueue<Integer> toRemove = new PriorityQueue<>(Comparator.reverseOrder());

        for (int i = 0; i < brackets.size(); i++) {
            if((selected & 1 << i) != 0) {
                Point bracketPair = brackets.get(i);
                toRemove.offer(bracketPair.x);
                toRemove.offer(bracketPair.y);
            }
        }

        StringBuilder removedExpression = new StringBuilder(initialExpression);
        while (!toRemove.isEmpty()) {
            int toRemoveIdx = toRemove.poll();
            removedExpression.deleteCharAt(toRemoveIdx);
        }

        String newExpression = removedExpression.toString();
        // 이미 저장된 수식과 다른 새로운 수식일 경우, 저장
        if(!expressions.contains(newExpression)) {
            expressions.offer(newExpression);
        }
    }
}