[모의 SW 역량테스트] 숫자 만들기

숫자 만들기

N개의 숫자가 주어지고 N-1개의 연산자 카드가 주어진다.

숫자 사이에 연산자 카드를 끼워 넣어 다양한 결과값을 구해보기로 한다.

단, 수식을 계산할 때 연산자의 우선순위는 고려하지 않는다.

결과의 최대값과 최소값의 차이를 구하시오.

---

풀이

1. 주어진 연산자 순서의 모든 경우의 수를 구한다.
   • 반복문을 통해 연산자의 개수가 0이 아닐 경우에만 선택을 할 수 있도록 한다.
   • 선택한 연산자는 char배열에 저장을 한다.
   • idx가 연산자의 개수만큼 선택되었다면 return한다.
2. 주어진 연산자 순서대로 계산한다.
   • sum에 맨 처음 숫자를 저장한다.
   • 저장된 연산자 배열과 숫자배열을 반복을 통해 순서대로 계산한다.
3. 최대값과 최소값을 구한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution숫자만들기 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			int[] cal = new int[4];
			int[] number = new int[N];
			
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			
			for(int i = 0; i < 4; i++) {
				cal[i] = Integer.parseInt(st1.nextToken());
			}
			
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			
			for(int i = 0; i < N; i++) {
				number[i] = Integer.parseInt(st2.nextToken());
			}
			
			max = Integer.MIN_VALUE;
			min = Integer.MAX_VALUE;
			
			recur(cal, 0, new char[N-1], number);
			
			System.out.println("#"+tc+" "+ (max - min));
			
		}
		
		
	}
	static int N;
	
	static int max;
	static int min;
	
	
	static void recur(int[] cal, int idx, char[] result, int[] number) {
		if(idx >= N-1) {

			int ans = calculate(result, number);
			
			max = Math.max(ans, max);
			min = Math.min(ans, min);
			
			
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			if(cal[i] != 0) {
				cal[i]--;
				
				if(i == 0 ) {
					result[idx] = '+';
				}else if(i==1) {
					result[idx] = '-';
				}else if(i==2) {
					result[idx] = '*';
				}else {
					result[idx] = '/';
				}
				recur(cal, idx+1, result,number);
				cal[i]++;
			}else {
				continue;
			}
		}
		
	}
	
	static int calculate(char[] result, int[] number) {
		int sum = number[0];
		
		for(int i = 1; i < N; i++) {
			if(result[i-1] == '+') {
				sum+=number[i];
			}else if(result[i-1] == '-') {
				sum-=number[i];
			}else if(result[i-1] == '*') {
				sum*=number[i];
			}else {
				sum/=number[i];
			}
		}
		
		return sum;
	}

}