[SWEA]SWEA 모의 4008 숫자만들기

SWEA 모의 4008 숫자 만들기

 

 

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH

SW Expert Academy

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/AlZzI73F--E

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

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

/**
 * @author 은서파
 * @since 2022/09/25
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH
 * @git
 * @youtube
 * @performance 31,096 kb, 143 
 * @category #순열
 * @note
 */

public class SWEA_모의_4008_숫자만들기 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static int T;
    private static int N;
    private static int[] opers;
    private static int[] nums;
    private static int MIN, MAX;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        T = Integer.parseInt(input.readLine());
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(input.readLine());
            opers = new int[N - 1];
            tokens = new StringTokenizer(input.readLine());
            for (int i = 0, o = 0; i < 4; i++) {
                int cnt = Integer.parseInt(tokens.nextToken());
                for (int c = 0; c < cnt; c++) {
                    opers[o++] = i;
                }
            }
            //System.out.println("연산자 배열: "+ Arrays.toString(opers));
            nums = new int[N];
            tokens = new StringTokenizer(input.readLine());
            for (int n = 0; n < N; n++) {
                nums[n] = Integer.parseInt(tokens.nextToken());
            }
            //System.out.println("숫자판: "+ Arrays.toString(nums));

            MIN = Integer.MAX_VALUE;
            MAX = Integer.MIN_VALUE;
            makePermutation(0, new boolean[N - 1], new int[N - 1]);

            output.append(String.format("#%d %d%n", t, MAX - MIN));

        }
        System.out.println(output);
    }

    static void makePermutation(int nth, boolean[] visited, int[] selected) {
        if (nth == N - 1) {
            // 순열 완성 --> 계산
            //System.out.println(Arrays.toString(selected));
            int result = calc(selected);
            MIN = Math.min(MIN, result);
            MAX = Math.max(MAX, result);
            return;
        }

        for (int i = 0; i < opers.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                selected[nth] = opers[i];
                makePermutation(nth + 1, visited, selected);
                visited[i] = false;
            }
        }
    }

    static int calc(int[] opers) {
        int num = nums[0];
        for (int i = 0; i < opers.length; i++) {
            int oper = opers[i];
            if (oper == 0) {
                num += nums[i + 1];
            } else if (oper == 1) {
                num -= nums[i + 1];
            } else if (oper == 2) {
                num *= nums[i + 1];
            } else {
                num /= nums[i + 1];
            }
        }
        return num;
    }

    // REMOVE_START
    private static String instr = "10\n"
                                  + "5\n"
                                  + "2 1 0 1\n"
                                  + "3 5 3 7 9\n"
                                  + "6\n"
                                  + "4 1 0 0\n"
                                  + "1 2 3 4 5 6 \n"
                                  + "5\n"
                                  + "1 1 1 1\n"
                                  + "9 9 9 9 9 \n"
                                  + "6\n"
                                  + "1 4 0 0\n"
                                  + "1 2 3 4 5 6 \n"
                                  + "4\n"
                                  + "0 2 1 0\n"
                                  + "1 9 8 6\n"
                                  + "6\n"
                                  + "2 1 1 1\n"
                                  + "7 4 4 1 9 3 \n"
                                  + "7\n"
                                  + "1 4 1 0\n"
                                  + "2 1 6 7 6 5 8 \n"
                                  + "8\n"
                                  + "1 1 3 2\n"
                                  + "9 2 5 3 4 9 5 6 \n"
                                  + "10\n"
                                  + "1 1 5 2\n"
                                  + "8 5 6 8 9 2 6 4 3 2 \n"
                                  + "12\n"
                                  + "2 1 6 2\n"
                                  + "2 3 7 9 4 5 1 9 2 5 6 4 ";
    // REMOVE_END
}