2020 카카오 수식 최대화 자바

문제는 다음과 같다.
https://school.programmers.co.kr/learn/courses/30/lessons/67257

풀이는 다음과 같다.

import java.util.*;

class Solution {
    static int[] selected = {0, 1, 2};
    static boolean[] visited = new boolean[3];
    static String[] want = {"+", "-", "*"};
    static long answer = 0;
    static List<String> tokens; 
    
    public long solution(String expression) {
        
        
        
        backTracking(0, expression);
        
        return answer;
    
    }
    
    
    
    static void backTracking(int depth, String expression) {
        if(depth == 3) {
            
            StringTokenizer st = new StringTokenizer(expression, "+-*", true);
            tokens = new ArrayList<>();
            while(st.hasMoreTokens()) {
                tokens.add(st.nextToken());
            }
            
            long v = Math.abs(calc1(tokens));
            if(answer < v) {
                answer = v;
                return;
            }
        }
        
        for(int i = 0 ; i < 3 ; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            selected[depth] = i;
            backTracking(depth+1, expression);
            visited[i] = false;
        }
    }
    
    static long calc1(List<String> tokens) {
        
        for(int j = 0 ; j < 3 ; j++) {
            String op  = want[selected[j]];
            
            for(int i = 0 ; i < tokens.size() ; i++) {
                if(tokens.get(i).equals(op)) {
                    long n1 = Long.parseLong(tokens.get(i-1));
                    long n2 = Long.parseLong(tokens.get(i+1));
                    long n3 = calc2(n1, n2, op);
                    tokens.remove(i-1);
                    tokens.remove(i-1);
                    tokens.remove(i-1);
                    tokens.add(i-1, String.valueOf(n3));
                    i--;
                }
            }
        }
        return Long.parseLong(tokens.get(0));
        
    }
    
    
    static long calc2(long n1, long n2, String op) {
		long res = 0;
		switch(op) {
		case "+" :
			res = n1 + n2;
			break;
		case "-" :
			res = n1 -n2;
			break;
		case "*" :
			res = n1 * n2;
			break;
		}
		
		return res;
	}
}

calc1은 다음과 같은 함수이다.

3, +, 2, -, 1, *, 3 의 List<String> 이 있고

String op = want[selected[j]]; 를 통해 내가 원하는 연산자를 뽑는다.
(selected[j] 의 숫자에 따라 뽑히는 연산자가 다르다, 즉 여기서 완탐 백트래킹.)
// 예를 들어 0, 1, 2 || 0, 2, 1 ..... 이러한 순서에 따라 뽑히는 연산자가 다름.

예를 들어 +, -, * 우선순위대로 뽑았다고 하면,

	+ 차례에서 해당 List를 탐색하며
    3 + 2 - 1 * 3 ----> 5 - 1 * 3
    
    - 차례에서 해당 List를 탐색하며
    5 - 1 * 3 ----> 4 * 3
    
    * 차례에서 해당 List를 탐색하며
    4 * 3 ----> 12
    
여기까지 오고
return Long.parseLong(tokens.get(0)); 에 의해 12가 출력된다.

calc2은 다음과 같은 함수이다.
숫자 두개, 연산자를 받아 해당 연산 결과를 보여준다.

backTracking은 연산자의 우선순위를 바꿔가며 calc1을 사용해
최댓값을 찾아주는 함수이다.

구현이 약간 난이도 있고,
연산자에 관한 완탐 문제를 풀기에 참 좋은 예제라고 생각한다.

유의해야 할 점
백트래킹 함수의

if(depth == 3) {
            
            StringTokenizer st = new StringTokenizer(expression, "+-*", true);
            tokens = new ArrayList<>();
            while(st.hasMoreTokens()) {
                tokens.add(st.nextToken());
            }
            
            long v = Math.abs(calc1(tokens));
            if(answer < v) {
                answer = v;
                return;
            }
        }

이 부분을 유의해야 한다.
위에서 보여준 내용대로,
List<String>은 calc1 함수를 거치면 변형되므로,
해당 내용을 숙지하여
각각 값을 구해야 할 때 마다 (depth == 3)
새로운 List<String>를 만들어 주어야 한다.