[SWEA 4008] 숫자 만들기 (Jav a)

SWEA 4008 숫자 만들기

문제풀이

• 주어진 연산자를 모두 사용하여 만들 수 있는 모든 순서를 구한다.
• 연산을 수행하고 최댓값과 최솟값의 차이를 구한다.
• 연산자의 개수가 주어진 상황이기에 카운팅배열을 사용하였다.
• 어떤 것의 순열을 구할지 잘 생각하자 (숫자 또는 연산자)

구현코드

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

public class Solution {
	
	static int[] op;
	static int[] cnt;
	static int[] numbers;
	static int N, T, min, max, ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		
		for(int t = 1 ; t <= T ; ++t) {
			N = Integer.parseInt(br.readLine());
			
			numbers = new int[N];
			op = new int[N - 1];
			cnt = new int[4];
			min = Integer.MAX_VALUE;
			max = Integer.MIN_VALUE;
			ans = 0;
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < 4 ; ++i) {
				cnt[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < N ; ++i) {
				numbers[i] = Integer.parseInt(st.nextToken());
			}
			
			permutation(0);
			
			ans = max - min;
			
			System.out.println("#" + t + " " + ans);
		}
		
	}

	private static void permutation(int idx) {
		
		if(idx == N - 1) {
			int result = cal();
			
			min = min > result ? result : min;
			max = result > max ? result : max;
			
			return;
		}
		
		for(int i = 0 ; i < 4 ; ++i) {
			if(cnt[i] > 0 ) {
				cnt[i]--;
				op[idx] = i;
				permutation(idx + 1);
				cnt[i]++;
			}
		}
	}

	private static int cal() {
		int result = numbers[0];
		int nidx = 1;
		
		for(int i = 0 ; i < N - 1 ; ++i) {
			switch(op[i]) {
			case 0:
				result += numbers[nidx++];
				break;
			case 1:
				result -= numbers[nidx++];
				break;
			case 2:
				result *= numbers[nidx++];
				break;
			case 3:
				result /= numbers[nidx++];
				break;
			}
		}
		
		return result;
	}
}