카카오인턴_프로그래머스_수식최대화

https://programmers.co.kr/learn/courses/30/lessons/67257

코딩테스트 연습 - 수식 최대화

연산자는 +, -, * 세가지이다.

문제를 읽어보면 연산자의 우선순위를 조합하여 주어진 식을 최대로(음수는 절대값) 하는 결과값을 구하는 문제이다.

주의 할점! 

1. 연산자 두개가 동일한 우선순위를 가질수없다.

2. 같은 연산자가 두개 이상이면 앞에있는 연산자부터 계산을 해준다.

 

풀이 접근!

주어진식에서 연산자를 빼내서 우선순위를 조합하여 계산을 해줄수도있겠지만  연산자가 3가지 뿐이므로 

모든 조합을 구한후 그에 맞게 계산을 해주었다.

 

총 6개 이므로 

1. + - *

2. + * - 

3. - + *

4. - * +

5. * + -

6. * - +

위와 같이 6개의 조합을 가질수있다. 

만약 주어진 식이 100+500-600+700 이라고 하자 * 연산자가없는데 위에 우선순위를 어떻게 적용하지 라는 생각이 들수도있다. 좀만 생각하보면 위에 주어진 6가지 우선순위대로 계산을 해주되 * 가 없으면 무시하고 다음 연산자로 넘어 가면되는 것이다.

 

위에 우선순위 4번 조합 으로 예를 들어보자. 

4 =>  - * + 이다.

첫번째 우선순위는 - 이므로 주어진 식 100+500-600+700 에서 -를 찾으면 계산해주고 값을 갱신해주면된다.  

결과는 100 + (-100) + 700 이된다.

두번째 우선순위는 * 이다. 하지만 주어진 식 100 + (-100) + 700 에 * 가 없으므로 다음 연산자인 + 로 넘어가면된다.

세번째 우선순위는 + 이다.

결과는 700 이된다. 

다음과같으 주어진 식에서 위에 6 가지 조합에 대하여 계산하고 최대값을 구해주면 되는 문제이다.

 

다음은 전체 코드이다.

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
        
    static char[] prior = {'+', '-', '*'};
	static boolean[] check = new boolean[3];
	static ArrayList<Long> nums = new ArrayList<Long>();
	static ArrayList<Character> ops = new ArrayList<Character>();
	static long answer;
    
     public static long solution(String expression) {
        answer = 0;
       
        String num = "";
        for(int i = 0; i < expression.length(); i++) {
        	if(expression.charAt(i) >= '0' && expression.charAt(i) <= '9') {
        		num+= expression.charAt(i);
        	}else {
        		nums.add(Long.parseLong(num));
        		num = "";
        		ops.add(expression.charAt(i));
        	}
        }
        nums.add(Long.parseLong(num));
        
        
        dfs(0, new char[3]);    
        return answer;
    }
    
    public static Long calc(Long num1, Long num2, char op) {
    	long num = 0;
    	switch (op) {
			case '+': {
				return num1 + num2;
			}
			case '-': {
				return num1 - num2;
			}
			case '*': {
				return num1 * num2;
			}
    	}
    	return num;
    }
    
    public static void dfs(int count, char[] p) {
    	if(count == 3) {
        	// 원본 ArrayList 를 복사해준다.
    		ArrayList<Long> cNums = new ArrayList<>(nums);
    		ArrayList<Character> cOps = new ArrayList<Character>(ops);
    		System.out.println(cNums.size() + " " + cOps.size());
    		
            // 우선순위에 맞게 계산. list index 주의!
            // 숫자는 연산자 보다 항상 1개가 많다.
    		for(int i = 0; i < p.length; i++) {
    			for(int j = 0; j < cOps.size(); j++) {
    				if(p[i] == cOps.get(j)) {
                    	// 리스트는 지울때 한칸씩밀리고 배열의 사이즈가 동적으로 변하므로
                        // (j 를 두번 remove 하고 j-- 처리를 해준것이다.)
    					Long res = calc(cNums.remove(j), cNums.remove(j), p[i]);
    					cNums.add(j, res);
    					cOps.remove(j);
    					j--;
    				}
    			}
    		}
    		answer = Math.max(answer, Math.abs(cNums.get(0)));
    		return;
    	}
    	
        // 모든 우선순위 조합구하기.
    	for(int i = 0; i < 3; i++) {
    		if(!check[i]) {
    			check[i] = true;
    			p[count] = prior[i];
    			dfs(count + 1, p);
    			check[i] = false;
    		}
    	}

    }
	
}