[2020 카카오인턴] 수식 최대화

문제출처: https://programmers.co.kr/learn/courses/30/lessons/67257

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

풀이법:

1) 주어진 3가지 연산자의 우선순위 순열을 구한다.

2) 구한 순열의 각 우선순위에 따라 식 계산함.

3) 계산하는 방법이 좀 지저분하긴 한데 사람이 연산 순위 지키면서 연산하는 방법이랑 똑같이 햇음

 

Comment:

1) 순열을 dfs로 구하는 법 배움

2) String으로 주어진 수식 계산하는 코드 짜면서 parsing 경험 좀 더 쌓은 듯

3) ArrayList 그냥 add remove 말고 index로 보통 array 처럼 쓰는게 좀 생소했음

4) postfix로 한 stack에 숫자 연산자 다 때려박고 계산하는 방법도 생각났는데 제대로 기억 안났음 그게 더 좋은 코드일 거 같긴하다

5) 코드가 너무 더럽다

 

import java.util.ArrayList;

class Solution {
    
    public static ArrayList<Long> operands;
	public static ArrayList<String> operators;
	public static String exp;
	public static long max = -1;
    
    public long solution(String expression) {
        
        operators = new ArrayList();
		operands = new ArrayList();
        getOp(expression);

        exp = String.valueOf(expression);

    	char[] ops = new char[operators.size()];
		
		for(int i = 0; i < operators.size(); i++) {
			ops[i] = operators.get(i).toCharArray()[0];
		}
        
        int n = operators.size();
		char[] output = new char[n];
		boolean[] visited = new boolean[n];
		
		operators = new ArrayList();
		
		makeList(expression);
		
		permutation(ops, output, visited, 0, n, n);
        
        return max;

		

    }
    
    //find operators in expression
	public static void getOp(String exp) {
		if(exp.contains("*")) {
			operators.add("*");
		}		
		if (exp.contains("+")) {
			operators.add("+");
		}if (exp.contains("-")) {
			operators.add("-");
		}
	}
	
    	
	public static void makeList(String expression) {
		char[] exp = expression.toCharArray();
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < exp.length; i++) {
			char c = exp[i];
			if('0'<= c && c <= '9') {
				sb.append(c);
			}else {
				operands.add(Long.valueOf(sb.toString()));
				sb.setLength(0);
				operators.add(c+"");
			}
		}
		operands.add(Long.valueOf(sb.toString()));
	}
    
    public static void permutation(char[] ops, char[] output, boolean[] visited, int depth, int n, int r) {
		if(depth == r) {
			System.out.println(output);
			calculate(output);

		}		
		for(int i = 0; i < n; i++) {
			if(visited[i] != true) {
				visited[i] = true;
				output[depth] = ops[i];
				permutation(ops, output, visited, depth + 1, n, r);
				visited[i] = false;
			}
		}
	}

	public static void calculate(char[] order) {
		
		ArrayList<Long> toperands = new ArrayList();
		ArrayList<String> toperators = new ArrayList();
		
		toperands.addAll(operands);
		toperators.addAll(operators);
		
		
		for(int i = 0; i < order.length; i++) {
			
			String cur = order[i] + ""; //현재 우선순위 연산자
			
			while(toperators.contains(cur)) {
				
				int index = toperators.indexOf(cur);
				long temp = calc(toperands.get(index), toperands.get(index + 1), cur);
				
				toperands.remove(index);
				toperands.remove(index);
				toperands.add(index, temp);
				
				toperators.remove(index);
			}
		}
		
		long result = Math.abs(toperands.get(0));
		
		System.out.println(result);

		if(max < 0) {
			max = result;
		}else {
			if(max < result) {
				max = result;
			}
		}
		
		
	}
	
	public static long calc(long op1, long op2, String operator) {
		long result = 0;
		
		if(operator.equals("+")) {
			result = op1 + op2;
		}else if(operator.equals("-")) {
			result = op1 - op2;
		}else if(operator.equals("*")) {
			result = op1 * op2;
		}
		return result;
	}
}