[백준] 15659번 : 연산자 끼워넣기 (3)

문제

15659번: 연산자 끼워넣기 (3)

 

접근 방식

기존의 연산자 끼워넣기 1, 2번 시리즈와 비슷하지만 연산자의 우선순위를 적용해야 해서

선택한 연산자들을 배열에 기록해 두었다 나중에 한 번에 연산을 해줘야 한다.

 

중간중간에 처리해서 빠르게 계산을 해보려 했는데 예제들은 통과가 되지만

제출하면 도무지 1 퍼에서 올라가질 않길래 포기하고 한 번에 연산을 해줬다.

 

기존 방식대로 각각의 연산자들을 선택할 수 있을 때 선택하는 방식으로 진행하면서

n-1개의 연산자를 선택했을 때 스택을 활용해서 우선순위대로 처리해 주면 된다.

 

덧셈과 뺄셈은 스택에 계속해서 쌓아두다가

곱셈과 나눗셈일 때 이전 값을 꺼내서 계산한 후에 스택에 결과를 넣어주고

모든 연산자를 다 처리한 후에 스택의 값들을 모두 꺼내면서 더해주면 된다.

 

풀이

public class Main {

	static int n, plus, minus, multi, div, max = -1000000001, min = 1000000001;
	static int[] arr;
	static char[] ops;

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

		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		ops = new char[n - 1];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());

		plus = Integer.parseInt(st.nextToken());
		minus = Integer.parseInt(st.nextToken());
		multi = Integer.parseInt(st.nextToken());
		div = Integer.parseInt(st.nextToken());

		solve(0);

		System.out.println(max + "\n" + min);
	}

	static void solve(int size) {
		if (size == n) {
			calcurate();
			return;
		}

		if (size == 0) {
			solve(size + 1);
		} else {
			if (plus != 0) {
				plus--;
				ops[size - 1] = '+';
				solve(size + 1);
				plus++;
			}

			if (minus != 0) {
				minus--;
				ops[size - 1] = '-';
				solve(size + 1);
				minus++;
			}

			if (multi != 0) {
				multi--;
				ops[size - 1] = '*';
				solve(size + 1);
				multi++;
			}

			if (div != 0) {
				div--;
				ops[size - 1] = '/';
				solve(size + 1);
				div++;
			}
		}
	}

	static void calcurate() {
		int result = 0;

		Stack<Integer> s = new Stack<>();

		s.push(arr[0]);

		for (int i = 0; i < n - 1; i++) {
			switch (ops[i]) {
				case '+': {
					s.push(arr[i + 1]);
					break;
				}
				case '-': {
					s.push(arr[i + 1] * -1);
					break;
				}
				case '*': {
					s.push(s.pop() * arr[i + 1]);
					break;
				}
				default: {
					s.push(s.pop() / arr[i + 1]);
					break;
				}
			}
		}

		while (!s.isEmpty()) {
			result += s.pop();
		}

		max = Math.max(max, result);
		min = Math.min(min, result);
	}
}