[백준] 14888번 연산자 끼워넣기

 n개의 피연산자와 n-1개의 연산자가 주어지면 연산자와 피연산자를 적절히 배치합니다. 적절히 배치해서 수식을 만드는데 수식을 계산해서 나오는 결과들의 최소값과 최대값을 구하는 문제입니다. 저는 재귀를 이용해서 문제를 해결했습니다. 연산자를 기준으로 최대 10번의 메서드 호출로 문제를 해결할 수 있기 때문에 재귀로해도 stackoverflow 에러가 발생하지 않을 것이라고 생각했습니다. 그러나 중복되는 연산을 제대로 처리해주지 못해서 시간이 오래 걸리는 문제가 있었습니다. 아래는 문제의 링크와 코드입니다.

- 문제 : https://www.acmicpc.net/problem/14888

- 소스 코드

import java.util.Scanner;

public class OperatorInsertion {

	int numOfOperand;
	int[] operand;
	int[] operators;
	int[] equation;
	Scanner sc;

	int min = 1000000001, max = -1000000001;

	void setValues() {
		sc = new Scanner(System.in);

		numOfOperand = sc.nextInt();
		operand = new int[numOfOperand];
		operators = new int[4];
		for (int i = 0; i < operand.length; i++) {
			operand[i] = sc.nextInt();
		}
		for (int i = 0; i < operators.length; i++) {
			operators[i] = sc.nextInt();
		}
		equation = new int[operand.length * 2 - 1];
		int next = 0;
		for (int i = 0; i < operand.length; i++) {
			equation[next] = operand[i];
			next += 2;
		}
	}

	void makeEquation(int equationIndex, int operator) {
		int remainOperators = 0;
		for (int i = 0; i < operators.length; i++) {
			remainOperators += operators[i];
		}
		if (remainOperators == 0) {
			solveEquation();
			equation[equationIndex] = 0;
			return;
		}

		for (int i = 0; i < operators.length; i++) {
			for (int j = 0; j < operators[i]; j++) {
				operators[i]--;
				equation[equationIndex+2] = getOperator(i);
				makeEquation(equationIndex + 2, i);
				operators[i]++;
			}
		}
	}
	
	char getOperator(int value){
		switch (value) {
		case 0:{
			return '+';
		}
		case 1:{
			return '-';
		}
		case 2:{
			return '*';
		}
		case 3:{
			return '/';
		}
		default:
			return '\0';
		}
	}

	void solveEquation() {
		int result = equation[0];
		for (int i = 1; i < equation.length; i++) {
			switch ((char) (equation[i])) {
			case '+': {
				i++;
				result += equation[i];
				break;
			}
			case '-': {
				i++;
				result -= equation[i];
				break;
			}
			case '*': {
				i++;
				result *= equation[i];
				break;
			}
			case '/': {
				i++;
				result /= equation[i];
				break;
			}
		}
		}
		
		if(min > result) min = result;
		if(max < result) max = result;
	}

	void solution() {
		setValues();
		for (int i = 0; i < operators.length; i++) {
			for (int j = 0; j < operators[i]; j++) {
				operators[i]--;
				equation[1] = getOperator(i);
				makeEquation(1, i);
				operators[i]++;
			}
		}
		System.out.println(max);
		System.out.println(min);
	}

	public static void main(String[] args) {
		OperatorInsertion m = new OperatorInsertion();
		m.solution();
	}

}