백준 14888번: 연산자 끼워넣기

문제 설명

• 주어진 숫자와 연산자로 만들 수 있는 가장 큰 수와 가장 작은 수를 구하는 문제입니다.

접근법

• 가능한 모든 수식을 전부 만들었습니다.
  • 순열을 통해 가능한 연산자의 조합을 모두 구했습니다.
• 문자열 수식을 계산해야 합니다.
  • 처음에는 Javascript의 eval을 활용했었습니다. 하지만 나누기 연산에서 몫만 취하는 부분이 원하는대로 되지 않아 다른 방법으로 변경했습니다.

정답

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

public class Main {
	static int N, min, max;
	static boolean[] v;
	static char[] oper_array, oper;
	static int[] nums;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		min = Integer.MAX_VALUE; // 최소값을 담는 변수입니다.
		max = Integer.MIN_VALUE; // 최대값을 담는 변수입니다.
		v = new boolean[N - 1]; // 순열에서 해당 숫자를 사용했는지 판별하는 변수입니다.
		nums = new int[N]; // 문제에서 주어지는 숫자를 담는 배열입니다.
		oper_array = new char[N - 1]; // 순열에서 만들어지는 연산자 조합을 담는 변수입니다.
        // nums에 숫자를 담습니다.
		StringTokenizer st = null;
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		oper = new char[N - 1]; // 사용할 수 있는 연산자를 담는 변수입니다.
	
    	// 연산자를 담습니다.
		char[] operation = { '+', '-', '*', '/' };
		int cnt = 0;
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < 4; i++) { // 연산자 종류만큼 반복합니다
			int inp = Integer.parseInt(st.nextToken()); // 해당 연산자가 몇개 들어있는지를 받습니다.
			for (int j = 0; j < inp; j++) {
				oper[cnt++] = operation[i];
			}
		}
		permu(0);
		System.out.println(max);
		System.out.println(min);

	}

	public static void permu(int depth) {
		if (depth == N - 1) {
        	//가장 앞에 값을 추가하고 빼기 위해 Deque를 사용했습니다.
			Deque<Integer> num_lst = new LinkedList<Integer>();
			Deque<Character> oper_lst = new LinkedList<Character>();

			// nums와 oper_array를 Deque로 변환합니다.
			for (int i = 0; i < oper_array.length; i++) {
				num_lst.add(nums[i]);
				oper_lst.add(oper_array[i]);
			}
            // 연산자보다 숫자가 하나 더 많기 때문에 마지막 숫자는 따로 넣어줍니다.
			num_lst.add(nums[nums.length - 1]);
			
            // 앞에 두 숫자를 연산한 뒤 다시 앞에 넣습니다.
			for (int i = 0; i < N - 1; i++) {
				char oper = oper_lst.pollFirst();
				int num1 = num_lst.pollFirst();
				int num2 = num_lst.pollFirst();
                
                // 연산자 종류에 맞는 연산을 한 뒤 앞으로 넣습니다.
				if (oper == '+') {
					num_lst.addFirst(num1 + num2);
				} else if (oper == '-') {
					num_lst.addFirst(num1 - num2);
				} else if (oper == '*') {
					num_lst.addFirst(num1 * num2);
				} else if (oper == '/') {
					num_lst.addFirst(num1 / num2);
				}
			}

			max = Math.max(num_lst.getFirst(), max);
			min = Math.min(num_lst.getFirst(), min);

			return;
		}

		for (int i = 0; i < N - 1; i++) {
			if (v[i])
				continue;
			v[i] = true;
			oper_array[depth] = oper[i];
			permu(depth + 1);
			v[i] = false;
		}

	}

}