[SWEA] 4008번 [모의 SW 역량테스트] 숫자 만들기 - 자바

• 문제 : 주어진 연산자 카드를 사용하여 수식을 계산했을 때 그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고, 두 값의 차이를 출력한다.
• 접근방법
  • 연산자의 순서에 대해 모든 경우의 수를 따진다. => 순열
    •  각 연산자의 개수 '+' 2 개, '-' 1 개, '*' 0 개, '/' 1 개의 경우
    • 위와 같은 경우에는 {+, +, -, /} , {+, -, +, /}, {/, -, +, +} 등의 연산자 순서에 대해 경우의 수를 나타낼 수 있다.
  • 위에서 경우의 수를 구한뒤 이에 대해 사칙연산을 수행하여 결과값을 도출해낸다.
• 구현 코드
  • 아래의 permutation()함수의 output 배열에서는 입력으로 받았던 연산자 배열에 대한 인덱스의 순서가 저장된다.

public class Solution_4008 {

	
	private static int N;//숫자의 개수
	private static int[] operation;//순서대로 '+', '-', '*', '/'의 개수
	private static int[] countOperation;//임시 카운트 배열 
	private static int max, min;
	private static int[] num;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		
		for (int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine());
			operation = new int[4];
			
			max = Integer.MIN_VALUE;
			min = Integer.MAX_VALUE;
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < operation.length; i++) {
				operation[i] = Integer.parseInt(st.nextToken());
			}
		
			countOperation = new int[4];
			
			num = new int[N];
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				num[i] = Integer.parseInt(st.nextToken());
			}
			
			permutation(new int[N-1], 0);

			bw.write("#" + test_case + " " + (max-min));
			bw.newLine();
		}//end of testcase
		
		bw.flush();
		bw.close();
	}
	
	
	//순열을 통해 연산자 순서를 정함
	private static void permutation(int[] output, int count) {
		if(count == N-1) {
			calculate(output);
			return;
		}
		
		for (int i = 0; i < 4; i++) {
			if(operation[i] != 0 && countOperation[i] < operation[i]) {
				output[count] = i;
				countOperation[i]++;
				permutation(output, count+1);
				countOperation[i]--;
			}
		}
	}
	
	//연산자 순서를 토대로 사칙연산 수행
	private static void calculate(int[] output) { 
		int temp = num[0];
		
		for (int i = 0; i < output.length; i++) {
			//순서대로 '+', '-', '*', '/'
			if(output[i] == 0) {
				temp += num[i+1];
			}else if(output[i] == 1) {
				temp -= num[i+1];
			}else if(output[i] == 2) {
				temp *= num[i+1];
			}else {
				temp /= num[i+1];
			}
		}
		
		if(max < temp) {
			max = temp;
		}
		if(min > temp) {
			min = temp;
		}
	}

}