링크
풀이
✅순열 재귀 풀이
- 연산자의 순서에 따라 답이 달라지므로 순열을 사용한다.
- 같은 연산자가 중복 존재하므로 ->
같은 것이 있는 순열참고 링크같은 것이 있는 순열
순열이 같은 것이 포함된 원소들을 나열하는 경우의 수는 나열하는 원소의 팩토리얼에 중복된 원소들의 팩토리얼을 나누어주면 된다.
예를 들어 aaabb와 같은 경우 a가 3개이고 b가 2개이므로 5!을 3!와 2!로 나누어주면 된다. - 가지치기: 연산들에 대해서 순열을 구할 때, 해당 cnt위치에서 같은 연산자가 다시 뽑힌 다면 같은 순서를 가진 경우의 수가 반복된다. 따라서 재귀 리턴을 받아서 원상복귀할 때 임시변수에 해당 값을 저장해두고 다음 차례의 값과 비교해서 같다면 다음으로 넘긴다.
이와 같은 과정은 맨 처음에 초기화할 때, 연산자별로 연속적으로 넣었기 때문에 가능하다.
✅next_permutation을 이용한 풀이
next_permutation 순열
- 가지치기x
- 어차피 다 구해야 할 때
- ⭐⭐⭐ 중복순열에서 중복되지 않은 것을 구할 때
재귀 순열 코드
package SWEA_AD;
import java.io.*;
import java.util.StringTokenizer;
public class Solution_4008_숫자만들기 {
private static int N;
private static int[] arr;
private static int[] operations;
private static boolean[] vis;
private static int[] permArr;
private static int max;
private static int min;
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());
arr = new int[N];
operations = new int[N-1];//1 2 3 4 순으로 + - * /
vis = new boolean[N];
permArr= new int[N-1];
int idx = 0;
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < 4; i++) {
int size = Integer.parseInt(st.nextToken());
for(int j =0 ; j < size ; j++) {
operations[idx++] = i+1;
}
}
st = new StringTokenizer(br.readLine(), " ");
for(int i =0 ; i < N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;
perm(0);
System.out.println("#" + tc + " " + (max - min));
}//end of testCase
}
private static void perm(int cnt) {
if(cnt == N-1) {
int tmpRes = check();
if(tmpRes > max) {
max = tmpRes;
}
if(tmpRes < min) {
min = tmpRes;
}
return;
}
int duplication = 0;
for(int i = 0; i < N-1; i++) {
if(!vis[i]) {
if(duplication == operations[i]) continue;
vis[i]= true;
permArr[cnt] = operations[i];
perm(cnt+1);
vis[i] = false;//원상복귀
duplication = operations[i];
}
}
}
private static int check() {
int tmpRes = arr[0];
for(int i = 0; i < N -1; i++) {
int tmpNum = arr[i+1];
int tmpOper = permArr[i];
switch (tmpOper) {
case 1:
tmpRes += tmpNum;
break;
case 2:
tmpRes -= tmpNum;
break;
case 3:
tmpRes *= tmpNum;
break;
case 4:
tmpRes /= tmpNum;
break;
default:
break;
}
}
return tmpRes;
}
}
next_permutation 풀이
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. 10. 4.
* @see
* @git
* @youtube
* @performance 28,320 kb, 138 ms
* @category #
* @note
*/
public class SWEA_모의_4008_숫자만들기 {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder output = new StringBuilder();
static StringTokenizer tokens;
static int T;
static int N;
static int[] opers;
static int[] nums;
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());
tokens = new StringTokenizer(input.readLine());
opers = new int[N - 1];
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;
}
}
tokens = new StringTokenizer(input.readLine());
nums = new int[N];
for (int n = 0; n < N; n++) {
nums[n] = Integer.parseInt(tokens.nextToken());
}
//System.out.println(Arrays.toString(opers)+" : "+Arrays.toString(nums));
// 입력 완료
MIN = Integer.MAX_VALUE;
MAX = Integer.MIN_VALUE;
//next permutation 순열 구하기
// 1. 요소를 정렬한다.
/*
Arrays.sort(opers);
// 2. 반복을 통해서 순열을 사용한다.
do {
//System.out.println(Arrays.toString(opers));
int result = calc(opers);
MAX = Math.max(MAX, result);
MIN = Math.min(MIN, result);
} while (nextPermutation());
*/
makePermutation(0, new boolean[N - 1], new int[N - 1]);
output.append(String.format("#%d %d%n", t, MAX - MIN));
}// T.C
System.out.println(output);
}
static void makePermutation(int nth, boolean[] visited, int[] selected) {
if (nth == N-1 ) {
int result = calc(selected);
MAX = Math.max(MAX, result);
MIN = Math.min(MIN, 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;
}
}
}
// 1 +2 *3
static int calc(int[] selected) {
int num = nums[0];
for (int i = 0; i < opers.length; i++) {
int oper = selected[i];
int next = nums[i + 1];
if (oper == 0) { // +
num += next;
} else if (oper == 1) { // -
num -= next;
} else if (oper == 2) { // *
num *= next;
} else {
num /= next;
}
}
return num;
}
// 1, 2, 3, 4 ==> 4, 3, 2, 1
static boolean nextPermutation() {
int lastPeak = opers.length - 1;
while (lastPeak > 0 && opers[lastPeak - 1] >= opers[lastPeak]) {
lastPeak--;
}
// 4, 3, 2, 1
if (lastPeak == 0) { // 이미 마지막인 상황 -- 다음은 없다.
return false;
}
int gtBeforeLastPeak = opers.length - 1;
while (opers[lastPeak - 1] >= opers[gtBeforeLastPeak]) {
gtBeforeLastPeak--;
}
swap(lastPeak - 1, gtBeforeLastPeak);
for (int reverseIdx = opers.length - 1; lastPeak < reverseIdx;) {
swap(lastPeak++, reverseIdx--);
}
return true;
}
static void swap(int a, int b) {
int temp = opers[a];
opers[a] = opers[b];
opers[b] = temp;
}
// 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
}
바른 자세로 코딩합니다 👦🏻💻