SWEA 4008 숫자 만들기(JAVA) 🧮

구조화

• 연산자 갯수 배열을 순열 사용하여 경우의 수 만들기
• Boolean 배열 대신 배열의 값을 --하면서 중복 해결
• 연산자는 0: +, 1: -, 2: *, 3: / 로 정함
  • switch문 사용하여 각각의 연산자로 계산

소스 코드

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

public class Solution {

    static int T, N;
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;
    
    // 0: +, 1: -, 2: *, 3: /
    static int[] operator;
    static int[] numbers;
    static int[] result;

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) 
        {
            N = Integer.parseInt(br.readLine());
            
            operator = new int[4];
            numbers = new int[N];
            result = new int[N-1];

            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            // 연산자
            for (int i = 0; i < 4; i++) 
            {
            	operator[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            // 수식에 사용되는 숫자
            for (int i = 0; i < N; i++) 
            {
                numbers[i] = Integer.parseInt(st.nextToken());
            }
            
            perm(0);
            
            System.out.printf("#%d %d%n",t,max-min);
        }
    }

    private static void perm(int cnt) { 
    
    	// cnt: 직전까지 뽑은 순열애 포함된 수의 개수, cnt+1번째 순열에 포함될 수를 뽑기
    	// 중복인 값 처리해줘야됨
    	
    	
        if (cnt == N-1) {	
            calMinMax();    
            return;
        }
        // 가능한 모든 수에 대해 시도
        for (int i = 0; i < 4; i++) // 선택지
        {
            // 시도하는 수가 선택되었는 지 판단
            if(operator[i] <= 0) continue;
            // 선택되지 않았다면 수를 사용
            result[cnt] = i;
            operator[i]--;
            
            // 다음 수 뽑으러 가기
            perm(cnt+1);
            // 사용했던 수에 대해 선택을 되돌리기
            operator[i]++;
        }
    }

	private static void calMinMax() {
		
        int cal = numbers[0];
        
        // 연산 경우의 수 토대로 min, max 찾기
        for (int i = 0; i < N-1; i++) 
        {
            switch (result[i]) {
			// +
            case 0:
				cal = cal + numbers[i+1];
				break;
            case 1:
				cal = cal - numbers[i+1];
				break;
            case 2:
				cal = cal * numbers[i+1];
				break;
            case 3:
				cal = cal / numbers[i+1];
				break;

			default:
				break;
			}
            
        }
        min = Math.min(cal, min);
        max = Math.max(cal, max);
	}

}