[Baekjoon] 괄호 추가하기 2

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

import java.io.*;
import java.util.*;

public class Main {
    private static int N;
    private static int answer = Integer.MIN_VALUE;
    private static String input;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    private static void sol() {
        List<String> expression = splitExpression();
        List<String> result = new ArrayList<>();

        answer = calculate(expression);

        dfs(expression, result);
    }

    private static void dfs(List<String> expression, List<String> result) {
        if (expression.size() <= 1) {
            result.addAll(expression);
            answer = Math.max(answer, calculate(result));
            return;
        }

        List<String> skipResult = new ArrayList<>(result);
        skipResult.add(expression.get(0));
        skipResult.add(expression.get(1));

        dfs(expression.subList(2, expression.size()), skipResult);

        List<String> newExpression = getExpressionExceptParenthesis(expression);
        List<String> newResult = getParenthesisResult(expression, result);

        dfs(newExpression, newResult);
    }

    private static List<String> getParenthesisResult(List<String> expression, List<String> result) {
        List<String> newResult = new ArrayList<>(result);

        int num1 = Integer.parseInt(expression.get(0));
        String op1 = expression.get(1);
        int num2 = Integer.parseInt(expression.get(2));

        switch (op1) {
            case "+":
                newResult.add(String.valueOf(num1 + num2));
                break;
            case "-":
                newResult.add(String.valueOf(num1 - num2));
                break;
            case "*":
                newResult.add(String.valueOf(num1 * num2));
                break;
        }

        if (expression.size() > 3) {
            newResult.add(expression.get(3));
        }

        return newResult;
    }

    private static List<String> getExpressionExceptParenthesis(List<String> expression) {
        List<String> newExpression = new ArrayList<>();

        for (int i = 0; i < expression.size(); i++) {
            if (i <= 3) {
                continue;
            }

            newExpression.add(expression.get(i));
        }

        return newExpression;
    }

    private static int calculate(List<String> result) {
        Deque<Integer> s = new ArrayDeque<>();

        for (int i = 0; i < result.size(); i++) {
            if (i == 0) {
                s.push(Integer.parseInt(result.get(i)));
                continue;
            } else if (result.get(i).equals("*")) {
                s.push(s.pop() * Integer.parseInt(result.get(i + 1)));
                i++;
                continue;
            } else if (result.get(i).equals("+")) {
                s.push(Integer.parseInt(result.get(i + 1)));
                i++;
                continue;
            } else if (result.get(i).equals("-")) {
                s.push(-Integer.parseInt(result.get(i + 1)));
                i++;
                continue;
            }
        }

        int sum = 0;

        for (int n : s) {
            sum += n;
        }

        return sum;
    }

    private static List<String> splitExpression() {
        List<String> expression = new ArrayList<>();

        for (int i = 0; i < input.length(); i++) {
            expression.add(String.valueOf(input.charAt(i)));
        }

        return expression;
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        input = br.readLine();
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.close();
    }
}

주요 개념

• 백트래킹

• 구현

풀이 과정

• 다양한 풀이가 있지만 나의 경우에는 DFS 매개변수로 매번 새로운 리스트를 넘겨주도록 했다.

  • 매번 새로운 리스트를 만들기 때문에 사실 백트래킹은 필요없다.

• 문제 조건에서 중첩 괄호가 불가능하고 괄호안에 하나의 기호만 들어가기 때문에 DFS 탐색에서 괄호로 묶은 경우는 newResult에 담고 괄호를 제외한 나머지를 newExpression에 담았다.

  • 여기서 newExpression이 채워지는 경우의 수가 몇가지 있다.

    • 비어있는 경우 = 1+2+3+4 에서 (1+2)+(3+4)와 같이 깔끔하게 괄호로 묶었을 경우

    • 1개만 있는 경우 = 1+2+3 에서 (1+2)+3 으로 묶여서 하나만 남은 경우

      • 위 코드에서 (1+2)+3 으로 묶인 경우 newResult에는 1+2+가 담긴다.

• 결국, 1+2+3+4 에서 (1+2)로 묶는 DFS와 1+를 스킵하는 DFS를 호출하면 된다.