/ BOJ

BOJ_14888_연산자끼워넣기_JAVA

문제 : 연산자끼워넣기

링크 : BOJ_14888_연산자끼워넣기

접근 방식

위치가 고정되어있는 숫자가 주어지고, 연산자의 개수가 숫자의 개수 -1개만큼 주어진다. 이 연산자의 계산은 우선순위법칙을 따르지 않는다. 주어진 연산자로 가능한 경우의 수 중에서 가능한 최댓값과 최솟값을 출력해야한다.

나는 이 문제를 연산자를 순열 완전탐색으로 구하여 숫자에 연산을 적용해보는 방법으로 풀었다.

풀이 방법

  1. 숫자의 개수 N값을 입력받아 숫자 개수만큼 1차우너 배열을 생성한다.

  2. 그 후 주어지는 덧셈, 뺄셈, 곱셈, 나눗셈의 개수를 입력받는데, 입력이 연산자의 개수, 즉 숫자로 주어지기 때문에, 주어진 숫자만큼 반복하여 연산자의 리스트(Character)에 추가해준다.

  3. 순열을 이용해 주어진 연산자 리스트로부터 가능한 연산자 배치의 경우의 수를 모두 찾는다.

  4. 순열 메서드의 기저조건에서, 만들어진 연산자의 배치대로 주어진 숫자배열을 대입하여 연산을 진행하고, 연산을 마친 후, 최댓값과 최솟값을 저장한다.

  5. 모든 순열이 탐색된 후 최댓값과 최솟값을 출력한다.

소스 코드


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

public class BOJ_14888_연산자끼워넣기 {
	static int[] nums;
	static int[] cal;
	static List<Character> operactor = new ArrayList<>();
	static char[] opPerm;
	static int max,min;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		StringTokenizer st = new StringTokenizer(in.readLine()," ");

		nums = new int[N];

		for(int i=0;i<N;i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(in.readLine()," ");

		// 덧셈
		int k = Integer.parseInt(st.nextToken());
		for(int i=0;i<k;i++) {
			operactor.add('+');
		}
		// 뺄셈
		k = Integer.parseInt(st.nextToken());
		for(int i=0;i<k;i++) {
			operactor.add('-');
		}
		// 곱셈
		k = Integer.parseInt(st.nextToken());
		for(int i=0;i<k;i++) {
			operactor.add('*');
		}
		// 나눗셈
		k = Integer.parseInt(st.nextToken());
		for(int i=0;i<k;i++) {
			operactor.add('/');
		}
		opPerm = new char[operactor.size()];
		max = Integer.MIN_VALUE;
		min = Integer.MAX_VALUE;
		perm(0,0);
		System.out.println(max);
		System.out.println(min);
	}

	static void perm(int cnt, int flag) {

		// 기저조건
		if(cnt == operactor.size()) {
			int num = nums[0];
			for(int i=0;i<nums.length-1;i++) {
				switch(opPerm[i]){
				case '+':
					num = num + nums[i+1];
					break;
				case '-':
					num = num - nums[i+1];					
					break;
				case '*':
					num = num * nums[i+1];
					break;
				case '/':
					num = num / nums[i+1];
					break;
				}
			}
			max = Math.max(max, num);
			min = Math.min(min, num);
			return;
		}


		// 유도파트

		for(int i=0,n=operactor.size();i<n;i++) {

			if((flag & 1<<i) != 0) {
				continue;
			}

			opPerm[cnt] = operactor.get(i);
			perm(cnt+1,flag | 1<<i);
		}

	}

}