백준 - 16637번(괄호 추가하기)

문제 출처: https://www.acmicpc.net/problem/16637

문제

• 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

• 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

• 수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

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

public class Main {

    private static int res = Integer.MIN_VALUE;

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

        int N = Integer.parseInt(reader.readLine());    // 수식의 길이
        StringBuilder sb = new StringBuilder(reader.readLine());

        subset(new StringBuilder(sb), 0);

        System.out.println(res);
    }

    private static void subset(StringBuilder sb, int idx) {
        if (idx >= sb.length() - 1) {
            Stack<String> stack = new Stack<>();

            // sb는 한 자리 정수가 보장된다.
            for (int i = 0; i < sb.length();) {
                char c = sb.charAt(i);
                if (c == '(') {
                    int temp = process(sb.substring(i + 1, i + 4));
                    if (!stack.isEmpty()) {
                        calc(stack, temp);
                    } else {
                        stack.push(temp + "");
                    }

                    i += 5;
                } else if (c == '+' || c == '-' || c == '*') {
                    stack.push(Character.toString(c));
                    i++;
                } else {    // 숫자의 경우
                    if (!stack.isEmpty()) {
                        calc(stack, c - '0');
                    } else {
                        stack.push(Character.toString(c));
                    }
                    i++;
                }
            }

            res = Math.max(res, Integer.parseInt(stack.pop()));

            return;
        }

        StringBuilder temp = new StringBuilder(sb);
        sb.insert(idx, "(").insert(idx + 4, ")");
        subset(sb, idx + 6);
        subset(temp, idx + 2);
    }

    private static void calc(Stack<String> stack, int num) {
        String temp = stack.peek();
        if (temp.equals("*") || temp.equals("+") || temp.equals("-")) {
            // 꺼내서 계산
            int b = num;
            String operator = stack.pop();
            int a = Integer.parseInt(stack.pop());

            switch (operator) {
                case "+": stack.push(a + b + ""); break;
                case "-": stack.push(a - b + ""); break;
                case "*": stack.push(a * b + ""); break;
            }
        }
    }

    private static int process(String sub) {
        int a = sub.charAt(0) - '0';
        int b = sub.charAt(2) - '0';
        char operator = sub.charAt(1);
        switch (operator) {
            case '+': return a + b;
            case '-': return a - b;
            default: return a * b;
        }
    }

}

• 조건을 설정해주는 부분에서 미흡하여 시간이 많이 흘렀다.
• 단순 구현 문제로 특별한 로직은 없다.
• 부분 집합을 이용하여 괄호가 들어갈 수 있는 모든 경우의 수를 다 만들고 각각 계산을 진행한다.
• 계산을 할 때는 스택을 이용해서 풀었는데, 이 문제는 괄호 안에 들어있는 형식이 일정하므로 일정한 규칙을 통해 풀 수 있었다.
• charAt() 메서드를 통해 각 자리씩 살피는데, 만약 이때 스택이 비었다면 이때 char는 무조건 정수값이다. 이 경우 바로 문자열로 변환하여 스택에 push() 한다.
• 만약 charAt() 값이 연산자라면 무조건 스택에 push() 하고, 정수일 경우에는 스택에 있는 연산자와 다른 피연산자를 pop() 하여 연산한 후 다시 스택에 push() 한다.
• 시작 괄호를 만난 경우, 괄호 내의 내용을 먼저 계산한 다음 스택에 값을 push() 하는데, 이때 스택이 비었으면 바로 push() 하지만, 스택이 비어있지 않은 경우 연산을 수행한 다음 결과를 스택에 push() 한다. 문제의 규칙상 숫자 뒤에 숫자가 바로 오는 경우는 없기 때문에 따로 조건을 체크하지 않고 진행하였다.