연산자 끼워넣기 [백준 14888][실버1][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

https://www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

Queue와 ArrayList를 이용해서 풀었다.

1.q에 숫자들을 입력받는다.

2. ArrayList에 연산자를 0,1,2,3 으로 치환하여 입력받는다.

3. ArrayList에 들어있는 요소들로 순열을 돌린다.

4. q를 하나 복사하여 하나씩 빼면서 주어진 연산자에 맞게 연산한다.

package Study0307;

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

public class 연산자끼워넣기 {
	public static int N;
	public static int num[];
	public static boolean visit[];
	public static ArrayList<Integer> list;
	public static Queue<Integer> q;
	public static int min = Integer.MAX_VALUE;
	public static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();

		visit = new boolean[N];
		
		q = new LinkedList<>();
		list = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			q.add(sc.nextInt());
		}
		int cnt= 0;
		for (int i = 0; i < 4; i++) {
			int num = sc.nextInt();
			for (int j = 0; j < num; j++) {
				list.add(cnt);
			}
			cnt++;
		}
		num = new int[list.size()];
		permutation(0);
		
		System.out.println(max);
		System.out.println(min);
	}
	public static void permutation(int cnt) {
		if(cnt == list.size()) {
			Queue<Integer> tempq = new LinkedList<>();
			tempq.addAll(q); //q복사
			int sum = tempq.poll();
			for (int i = 0; i < list.size(); i++) {
				switch(num[i]) {
					case 0: sum += tempq.poll(); break;
					case 1: sum -= tempq.poll(); break;
					case 2: sum *= tempq.poll(); break;
					case 3: sum /= tempq.poll(); break;
				}
			}
			min = Math.min(min, sum);
			max = Math.max(max, sum);
			return;
		}
		
		for (int i = 0; i < list.size(); i++) {
			if(!visit[i]) {
				visit[i] = true;
				num[cnt] = list.get(i);
				permutation(cnt+1);
				visit[i] = false;
			}
		}
	}
}