[SWEA 역량테스트 모의 A형] 4008. 숫자만들기 (Java)

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

SW Expert Academy

 

안녕하세요!

곧 A형 시험이 있어서 주말 내내 알고리즘을 풀고 있네요,, ㅎㅎㅎ

새로운 문제를 풀기보다는 풀어봤던 문제들을 복습하고 있어요. 힘드네요,,ㅋㅋㅋ

오늘은 SW역량테스트 모의 A형 숫자 만들기 문제입니다.

 

문제 풀이 프로세스

이 문제의 핵심은 가지치기입니다.

연산자를 숫자 사이사이에 배치하는 것은 순열을 이용하면 됩니다.

N개의 연산자를 일렬로 나열하는 것과 같죠.

 

1부터 N까지의 숫자를 나열하는 경우의 수는 N! 입니다.

첫 칸엔 숫자 N개가 올 수 있고, 그 다음 칸에는 N-1개가 올 수 있고 , ... 마지막 남은 칸엔 1개의 숫자가 올 수 있습니다.

 

하지만 아쉽게도 컴퓨터는 12!의 경우의 수를 1초만에 구하지 못합니다.

컴퓨터가 1초에 할 수 있는 연산이 약 1억 번 정도인데, 12!은 479,001,600 (약 4억 8천)번이기 때문이죠.

참고로 11! 은 399,168,00(약 4000만)번으로 순열이 가능합니다.

 

이 문제에서 N의 범위는 1~12이기 때문에 최악의 경우 시간 초과가 나게 됩니다.

 

어떻게 가지를 칠 수 있을까?

문제에서 주어지는 연산자의 개수를 배열로 받을 수 있습니다.

+, -, *, / 순서로 받는다면, [2, 1, 0, 1] 은 + 2개, - 1개, * 0개, / 1개입니다.

 

여기서 연산자를 사용할 때마다 연산자 배열에서 1개씩 감소시켜준다면,

뽑을 수 있는 총 가짓 수가 줄어드니 시간이 단축됩니다.

 

순열이 완성되고 다른 순열을 시도할 때에는 원래의 방식처럼 다시 개수를 하나 늘려줍니다.

 

여기서 주의할 것은 연산자를 뽑을 때 해당 연산자가 남아있지 않다면 continue를 해줘야 합니다.

 

---

자세한 풀이는 아래 풀이에 나와 있습니다.

어려운 부분이나 피드백이 있다면 댓글로 남겨주세요!

좋아요도 부탁드립니다 ㅎㅎㅎ :)

 

정답 코드

package A뿌수기;

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

/**
 * 시작시간: 7:22
 * 완료시간: 7:51
 * 풀이시간: 29m
 * 
 * 문제 설명
 * N개의 숫자 적혀있는 게임판
 * +, -, x, / 연산자 카드를 숫자 사이에 끼워넣어 결과 구하기
 * 연산자 우선순위 고려 x, 왼쪽에서부터 차례대로 계산
 * 
 * 수식의 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고, 두 값의 차이를 출력하라 ***
 * 
 * 3 <= N <= 12
 * 연산자 카드 개수 총합은 항상 N-1
 * 숫자는 1~9 정수
 * 연산자 카드 모두 사용
 * 나눗셈 -> 소숫점은 버림
 * int 가능
 * 
 * 생각나는 풀이
 * 연산자 배치 -> 순열 -> 12! 은 안된다. -> 가지치기가 필요하다.
 * 가지치기의 조건은? ***
 * 연산자를 사용할 때마다 개수를 하나씩 빼준다.
 *
 * 문제 풀이 프로세스
 * 0. 최솟값, 최댓값 변수 static 으로 생성
 * 1. 연산자 배열 생성 +, -, x, / 순서
 * 2. 담아줄 picked 배열 생성
 * 3. 하나씩 사용할 떄마다 개수 빼주기, 재귀호출 후 정답이 아니라면 개수 추가
 * 4. 순열이 완성되었다면?
 * 	 4-1. 최댓값, 최소값과 비교 후 넣어주기
 * 5. 최댓값 - 최솟값 차이 출력
 */

public class Solution_4008_숫자만들기 {
	static int[] operators = new int[4]; // +, -, *, / 
	static int[] picked;
	static int[] numbers; 
	static int N;
	
	static int min, max;
	public static void main(String[] args) throws NumberFormatException, IOException {
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			min = Integer.MAX_VALUE; // 최솟값 업데이트
			max = Integer.MIN_VALUE; // 최댓값 업데이트
			
			N = Integer.parseInt(br.readLine());
			numbers = new int[N]; //  숫자판 생성
			picked = new int[N-1]; // 순열로 뽑아줄 연산자 배열 생성
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 4; i++) {
				operators[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);
			sb.append("#").append(tc).append(' ').append(max - min).append('\n');
		}
		System.out.println(sb);
	}
	
	private static void permutation(int cnt) {
		if (cnt == N-1) { // 종료조건 : N-1개만큼 뽑았을 떄
			
			// 수식 계산 후 최솟값, 최댓값 업데이트
			// 1. 수식 계산
			int tmp = numbers[0]; // 첫번째 숫자 값 넣어주기
			for (int i = 1; i < N; i++) {
				int operator = picked[i-1];
				switch (operator) {
				case 0:
					tmp += numbers[i];
					break;
				case 1:
					tmp -= numbers[i];
					break;
				case 2:
					tmp *= numbers[i];
					break;
				case 3:
					tmp /= numbers[i];
					break;
				}
			}
			
			// 2. 최솟값, 최댓값 업데이트
			max = Math.max(max, tmp);
			min = Math.min(min, tmp);
			return;
		}
		
		for (int i = 0; i < 4; i++) {
			if(operators[i] == 0) continue; // 이 조건 추가 필수!!
			picked[cnt] = i; // i번째 연산자 뽑기
			operators[i]--; // 방금 뽑은 i번째 연산자 사용 체크
			permutation(cnt + 1); // 다음 뽑을 것은 재귀로 넘기기
			operators[i]++; // 정답이 나오지 않았다면 사용한 것 다시 되돌려주기
		}
		
	}

}