[Java] 백준 연산자 끼워넣기

1. 문제 분석

주어진 숫자에 연산자를 넣는 문제다.

연산자의 개수는 주어진 숫자 - 1 만큼 주어지므로 순열을 통해 연산자의 집합을 구하면 된다.

2. 구현

import java.util.*;
import java.io.*;

public class Solution {

	static int size;
	static int[] numArr;
	static ArrayList<Character> operList = new ArrayList<>();
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		size = Integer.parseInt(br.readLine());
		numArr = new int[size];
		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < size; i++) {
			numArr[i] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			int operSize = Integer.parseInt(st.nextToken());
			for (int j = 0; j < operSize; j++) {
				switch (i) {
				case 0: {
					operList.add('+');
					break;
				}
				case 1: {
					operList.add('-');
					break;
				}
				case 2: {
					operList.add('*');
					break;
				}
				default: {
					operList.add('/');
					break;
				}
				}
			}
		}
		int operSize = operList.size();
		perm(new char[operSize], new boolean[operSize], operSize, operSize, 0);
		System.out.println(max);
		System.out.println(min);
	}

	static void perm(char[] output, boolean[] visited, int n, int r, int depth) {
		if (r == depth) {
			calc(output);
			return;
		}
		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				output[depth] = operList.get(i);
				perm(output, visited, n, r, depth + 1);
				visited[i] = false;
				output[depth] = 0;
			}
		}
	}

	static void calc(char[] operArr) {
		int answer = numArr[0];
		for(int i = 1; i<size; i++) {
			switch(operArr[i-1]) {
			case '+':{
				answer += numArr[i];
				break;
			}
			case '-':{
				answer -= numArr[i];
				break;
			}
			case '*':{
				answer *= numArr[i];
				break;
			}
			case '/':{
				answer /= numArr[i];
				break;
			}
			}
		}
		max = Math.max(max, answer);
		min = Math.min(min, answer);
	}
}

switch가 많아서 그렇지 제일 중요한 부분은 perm이다.

백트래킹을 통해서 순열을 구했고 연산자 배열이 다 나오면 계산을 해주었다.

3. 마무리

싸피 알고리즘 시간에 풀었던 문제라고 생각했는데 아닌가보다.

중복순열?을 사용해야하나 싶어서 일단 순열로 돌려보자 했는데 시간초과도 안나오고 바로 통과됐다.