[백준, Java] 16637번 : 괄호 추가하기

🔗 문제 링크

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

😮 문제 해결 방법

문제에서 주의깊게 봐야하는 조건이 몇가지 있다.

1. 모든 연산자의 우선순위는 동일하기 때문에 수식 계산은 왼쪽 부터 차례로 계산한다.
2. 괄호 안에는 연산자가 한 개만 들어간다.

1번 조건을 충족하기 위해서 재귀함수 호출 시 마다 현재까지의 결과 값(ouput 파라미터)과 괄호 추가한 경우 결과값 혹은 다음 차례의 피연산자와 계산을 한 결과값을 다음 재귀 호출시 넣어주어야 한다.

2번 조건을 충족하기 위해서 **현재 차례로 부터 다음 차례와 다다음 차례 (index + 1, index + 2)**의 피연산자를 먼저 계산해준다. 그 후 현재까지의 결과 값과 다시 한번 계산 하면 괄호를 반영한 결과값을 구할 수 있다.

괄호를 사용한 결과값을 계산한 경우 index+2 까지의 피연산자까지 계산 해주었으므로, 재귀 호출 시 index + 2값을 넣어준다.

괄호를 계산하지 않고 일반 계산 단계만 진행하는 경우 현재 차례와 다음 차례 피연산자 값을 계산해 재귀 호출로 넣어준다.

정리하자면,

1. 괄호를 사용하는 경우 num[index + 1], op[index+1], num[index + 2]값을 계산 후 해당 값을 output, op[index]로 계산한다.
   • 이 때, index + 2 까지 계산 했으므로 index + 2를 넣어 재귀를 호출한다.
2. 괄호를 사용하지 않는 경우 output, op[index], num[index+1]값을 계산 후 index + 1를 넣어 재귀를 호출 한다.
3. 연산자를 모두 사용한 경우 최대값을 비교해 갱신한다.
4. 괄호 사용 배열 인덱스를 잘 조절해주는 것이 중요하다.

🚩 Java 코드

package com.algorithm.Baekjoon;

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

public class Main_16637_괄호_추가하기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] num = new int[N / 2 + 1];
        char[] op = new char[N / 2];

        char[] exp = br.readLine().toCharArray();
        for (int index = 0; index < N; index++) {
            if (index % 2 == 0) num[index / 2] = Integer.parseInt(String.valueOf(exp[index]));
            else op[index / 2] = exp[index];
        }

        int rst = getMaxResult(num, op);
        System.out.println(rst);

        br.close();
    }

    private static int getMaxResult(int[] num, char[] op) {
        result = Integer.MIN_VALUE;

        makeExp(num[0], 0, num, op);
        return result;
    }

    private static int result;

    private static void makeExp(int output, int index, int[] num, char[] op) {
        // 연산자 모두 사용한 경우
        if (index >= op.length) {
            // 최대값 갱신
            result = Math.max(result, output);
            return;
        }

        // 괄호 계산 하는 경우
        // 숫자 배열이 넘어가지 않도록
        if (index + 2 < num.length) {
            // 현재 숫자 배열 인덱스보다 다음 두개의 숫자의 괄호 계산
            int rst = calc(num[index + 1], op[index + 1], num[index + 2]);
            // 현재까지의 ouput 과 다음 두개 계산 값 계산
            makeExp(calc(output, op[index], rst), index + 2, num, op);
        }
        // 괄호 계산 하지 않는 경우
        // 현재까지의 output과 다음 숫자 계산
        int rst = calc(output, op[index], num[index+1]);
        makeExp(rst, index + 1, num ,op);
    }

    private static int calc(int prev, char operation, int post) {
        if (operation == '+') return prev + post;
        if (operation == '-') return prev - post;
        return prev * post;
    }
}