BAEK_16637_괄호 추가하기

07 Oct 2019 in Sidemenu / BaekJoon

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

16637. 괄호 추가하기

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Main_16637_괄호추가하기 {
	static int N, len, max = Integer.MIN_VALUE;
	static int[] v;
	static String expression;
	static ArrayList<String> calclist = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new FileReader("res/Main_16637_괄호추가하기.txt"));
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		expression = br.readLine();
		for (int i = 0; i < N - 2;) {
			calclist.add(calc(new String[] { String.valueOf(expression.charAt(i)),
					String.valueOf(expression.charAt(i + 1)), String.valueOf(expression.charAt(i + 2)) }));
			i += 2;
		}
		len = calclist.size();
		v = new int[len + 1];
		calcAns();
		for (int i = 1; i <= len / 2; i++) {
			selectBracket(0, 0, i);
		}
		System.out.println(max);
	}

	static void selectBracket(int idx, int nowcnt, int cnt) {
		if (nowcnt == cnt) {
			calcAns();
			return;
		}
		for (int i = idx; i < len; i++) {
			if (i == 0 && v[i] == 0) {
				v[i] = 1;
				selectBracket(i + 1, nowcnt + 1, cnt);
				v[i] = 0;
			} else if (v[i - 1] == 0) {
				v[i] = 1;
				selectBracket(i + 1, nowcnt + 1, cnt);
				v[i] = 0;
			}
		}

	}

	static void calcAns() {
		Stack<String> newExpstack = new Stack<>();
		for (int i = 0; i < N; i++) {
			if (v[i / 2] == 1) {
				newExpstack.add(0, calclist.get(i / 2));
				i += 2;
			} else {
				newExpstack.add(0, String.valueOf(expression.charAt(i)));
			}
		}
		while (newExpstack.size() != 1) {
			newExpstack.push(calc(new String[] { newExpstack.pop(), newExpstack.pop(), newExpstack.pop() }));
		}
		max = Math.max(max, Integer.parseInt(newExpstack.pop()));
	}

	static String calc(String[] calcarr) {
		switch (calcarr[1]) {
		case "+":
			return String.valueOf(Integer.parseInt(calcarr[0]) + Integer.parseInt(calcarr[2]));
		case "-":
			return String.valueOf(Integer.parseInt(calcarr[0]) - Integer.parseInt(calcarr[2]));
		case "*":
			return String.valueOf(Integer.parseInt(calcarr[0]) * Integer.parseInt(calcarr[2]));
		}
		return "";
	}
}