BJ 16637 괄호 추가하기 풀어보기 (Java)

1. 괄호 추가하기 문제 이해하기

길이가 N인 수식이 주어지고 그 수식에서 자유롭게 0개 이상의 괄호쌍들을 추가하여 계산한 값들 중 최댓값을 계산하는 문제입니다.

괄호 안에 괄호는 들어갈 수 없습니다.
연산자 우선순위는 따지지 않고, 괄호 안에 있는 식을 우선적으로 계산합니다.
괄호 안에는 (숫자 연산자 숫자)의 형태로, 연산자가 한 개만 있어야 합니다.

2. 괄호 추가하기 문제 해결 방법

1. 주어진 식을 연산자와 숫자로 나누어 각자 배열에 저장합니다.

2. 숫자 배열에서, 2개의 쌍 선택하기 조합을 계산합니다.(괄호를 직접 넣지 않고, 개념만 가져와 우선적으로 계산할 쌍들을 찾기 위함입니다.)
   예를 들어, 숫자가 5개이면, 2개의 쌍을 0개 선택할 수도 있고, 1개 선택할 수도 있고, 2개 선택할 수도 있습니다.
   각각의 경우를 for문을 사용하여 선택한 쌍들을 visited 배열에 true로 체크해둡니다.

3. 2에서 조합을 찾을 때마다 선택한 2개의 쌍마다 연산자 배열에서 idx에 맞는 연산자를 찾아와 우선적으로 계산을 하고, 주어진 식을 연산하였을 때 결과값을 최댓값과 비교하여 더 클 경우 갱신합니다.

3. 확인 안하면 틀리는 사항

1. 정답은 231보다 작고, -231보다 크다.
   -> 자료형 long을 사용합니다.

2. 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다.
   -> N이 1일 때 작성한 알고리즘이 제대로 돌아가는지 확인해 줍니다.

4. 전체 코드

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

public class Main_BJ_16637_괄호추가하기 {

	public static int N, numLen, operLen;
	public static long maxRet;
	public static char oper[];
	public static long num[];
	public static boolean visited[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		maxRet = Long.MIN_VALUE;
		operLen = N / 2;
		numLen = N - operLen;
		oper = new char[operLen];
		num = new long[numLen];
		visited = new boolean[numLen];
		int i1 = 0, i2 = 0;
		String input = br.readLine();
		for (int i = 0; i < N; i++) {
			if (i % 2 != 0) { // 연산자
				oper[i1++] = input.charAt(i);
			} else { // 숫자
				num[i2++] = input.charAt(i) - '0';
			}
		}
		if (N == 1) {
			maxRet = num[0];
		}
		// N개 중 2개 쌍 1개에서 N/2개 뽑기
		for (int r = 1; r <= N / 2; r++) {
			find(r, 0, 0);
		}
		System.out.println(maxRet);
	}

	private static void find(int r, int start, int cnt) {
		// N개 중 2개쌍 i개 뽑기
		if (cnt == r) {
			// visited 돼 있는 애들부터 계산했을 때 값 구하기
			maxRet = Math.max(maxRet, calculate());
			return;
		}
		for (int i = start; i < numLen - 1; i++) {
			visited[i] = true;
			visited[i + 1] = true;
			find(r, i + 2, cnt + 1);
			visited[i] = false;
			visited[i + 1] = false;
			find(r, i + 1, cnt);
		}
	}

	// visited 돼있는 애들부터 계산했을 때 값 구하기
	private static long calculate() {
		long total = 0;
		long ret[] = new long[numLen]; // 입력으로 받은 숫자 배열과 같은 배열을 만들어 줍니다.
		for (int i = 0; i < numLen; i++) {
			ret[i] = num[i];
		}
		for (int i = 0; i < numLen; i++) {
			if (visited[i]) {
				if (oper[i] == '+') {
					ret[i] = ret[i] + ret[i + 1]; // 쌍의 첫 번째 숫자 자리에 연산한 값으로 다시 넣어주고(갱신)
					ret[i + 1] = Long.MIN_VALUE; // 쌍의 두 번째 숫자 자리에는 연산이 이미 끝났다는 뜻으로 다른 값을 넣어줍니다.
				} else if (oper[i] == '*') {
					ret[i] = ret[i] * ret[i + 1];
					ret[i + 1] = Long.MIN_VALUE;
				} else { // -
					ret[i] = ret[i] - ret[i + 1];
					ret[i + 1] = Long.MIN_VALUE;
				}
				i++;
			}
		}
		total = ret[0];
		for (int i = 1; i < numLen; i++) {
			if (ret[i] == Long.MIN_VALUE) {
				continue;
			}
			if (oper[i - 1] == '+') {
				total += ret[i];
			} else if (oper[i - 1] == '*') {
				total *= ret[i];
			} else { // -
				total -= ret[i];
			}
		}
		return total;
	}

}