[삼성 SW Expert Academy] 4008. [모의 SW 역량테스트] 숫자 만들기 [JAVA]

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

---

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

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

SW Expert Academy

---

| 풀이 

1. 연산자의 순열 구하기  - DFS 
2. 해당 순서대로 연산을 진행하며, 최소 값 / 최대 값 갱신

• 연산자의 개수를 굳이 순열로 바꾸기 위해 [N-1] 크기의 배열에 하나씩 저장하는 바보같은 행동을 했다. ↓

            st = new StringTokenizer(br.readLine()," ");
			for( int i=0; i<4; i++) {
				input[i] = Integer.parseInt(st.nextToken());
				int tmp = input[i];
				for( int j=0; j<tmp ; j++) {
					cal[idx++] = i; // 0: +, 1: -, 2: *, 3: /
				} // 각 숫자 cal에 무엇인지 입력해놓기 
				
			} // 들어온 연산자 input

•  ↓ input 배열 하나만으로 가능하다.

• ↓ 순열과 계산을 아래처럼 매개변수로 처리할 수 있기 때문에

---

| 어려웠던 점

• 기존 코드 ( 실패 ) - 시간 초과 ->> 여기에서 어떻게 바꿔서 해결할 수 있는지 궁금하다.
• 최소값, 최대값 갱신할 때, 

			int ans = calculation();
			if ( ans < min ) min = ans;
			else if ( ans > max ) max = ans;

•  위 방식처럼 하면 안된다.. 사소한 것도 해결하기! ( 최소값 갱신이 안될 때 min 의 값을 저장해줘야 한다. )
• ex. 최소값 if ( ans < min ) else 조건문도 처리 해줘야한다.

package 알고리즘공부하기;

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

public class 숫자만들기_4008 {

	static int TC, N;
	static int[] number, cal, input, sel;
	static boolean[] visited;
	static int min, max, answer;
	
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		st = new StringTokenizer(br.readLine()," ");
		TC = Integer.parseInt(st.nextToken());
		
		for( int tc=1; tc<=TC; tc++) {
			
			st = new StringTokenizer(br.readLine()," ");
			N = Integer.parseInt(st.nextToken());
			int idx = 0;
			
			number = new int[N]; // 들어온 숫자 
			cal = new int[N-1]; // 연산자 
			visited = new boolean[N-1]; //연산자 방문 체크  
			input = new int[4];
			sel = new int[N-1]; // 선택된 연산자 
			min = Integer.MAX_VALUE;
			max = Integer.MIN_VALUE;
			
			st = new StringTokenizer(br.readLine()," ");
			for( int i=0; i<4; i++) {
				input[i] = Integer.parseInt(st.nextToken());
				int tmp = input[i];
				for( int j=0; j<tmp ; j++) {
					cal[idx++] = i; // 0: +, 1: -, 2: *, 3: /
				} // 각 숫자 cal에 무엇인지 입력해놓기 
				
			} // 들어온 연산자 input
			
			st = new StringTokenizer(br.readLine()," ");
			for( int i=0; i<N; i++) {
				number[i] = Integer.parseInt(st.nextToken()); 
			} // 들어온 숫자 input
			
			// 1. 최대 11개의 연산자 순서 정하기 - 순열
			perm(0);
			
			// 2. 앞에서 부터 계산하며 최소 값 & 최대 값 구하기
			answer = max - min;
			
			System.out.println("#"+tc+" "+answer);
		}
	}
	
	// 같은 숫자는 어떻게 안바꿀 수 있을까?
	private static void perm(int idx ) {
		
		if ( idx == N-1) {
			int ans = calculation();
			if ( ans < min ) min = ans;
			else if ( ans > max ) max = ans;
			
			return;
		}
		
		
		for( int i=0; i<N-1; i++) {
			
			if( visited[i]) continue;
			visited[i] = true;
			sel[idx] = cal[i];
			perm(idx+1);
			visited[i] = false;
			
		}
		
	}
	// number : 숫자
	// sel : 연산자
	private static int calculation() {
		
		int A = number[0]; 
		for( int i=0; i<N-1; i++) {
			int B = number[i+1];
			int c = sel[i];
			switch( c) {
				
			case 0:
				A += B;
				break;
			case 1:
				A -= B;
				break;
			case 2:
				A *= B;
				break;
			case 3:
				A /= B;
				break;
			default:
				break;
			}
		}
		return A;
	}
}

---

| 코드

package 알고리즘공부하기;

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

public class 숫자만들기_v2_4009 {

	static int TC, N;
	static int[] number, input;
	static int min, max, answer;
	
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		st = new StringTokenizer(br.readLine()," ");
		TC = Integer.parseInt(st.nextToken());
		
		for( int tc=1; tc<=TC; tc++) {
			
			st = new StringTokenizer(br.readLine()," ");
			N = Integer.parseInt(st.nextToken());
			
			number = new int[N]; // 들어온 숫자 
			input = new int[4];
			min = Integer.MAX_VALUE;
			max = Integer.MIN_VALUE;
			
			st = new StringTokenizer(br.readLine()," ");
			for( int i=0; i<4; i++) {
				input[i] = Integer.parseInt(st.nextToken());
				
			} // 들어온 연산자 input
			
			st = new StringTokenizer(br.readLine()," ");
			for( int i=0; i<N; i++) {
				number[i] = Integer.parseInt(st.nextToken()); 
			} // 들어온 숫자 number
			
			// 1. 최대 11개의 연산자 순서 정하기 - 순열
			perm(0, number[0]);
			
			// 2. 앞에서 부터 계산하며 최소 값 & 최대 값 구하기
			answer = max - min;
			
			System.out.println("#"+tc+" "+answer);
		}
	}
	
	// 같은 숫자는 어떻게 안바꿀 수 있을까?
	private static void perm(int idx, int value ) {
		
		if ( idx == N-1) {
//			if ( value < min ) min = value;
//			else if ( value > max ) max = value;
			min = Math.min(value, min);
			max = Math.max(value, max);
			return;
		}
		
		
		for( int i=0; i<4; i++) {
			
			if( input[i] > 0 ) {
				
				input[i]--;
				switch( i ) {
				
				case 0:
					perm( idx +1 , value + number[idx+1]);
					break;
				case 1:
					perm( idx +1 , value - number[idx+1]);
					break;
				case 2:
					perm( idx +1 , value * number[idx+1]);
					break;
				case 3:
					perm( idx +1 , value / number[idx+1]);
					break;
				default:
					break;
				}
				input[i]++;
			}
		}
		
	}
}

---

| 보완할 점

• 처음 순열구해서 답 도출 하는 과정에서 시간초과 발생 했는데, 백트래킹으로 어떻게 해결할 수 있을지 ?

---