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

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

---

연산 수식이 주어졌을 때, 연산의 우선순위를 정의해 가장 큰 수를 만들어 제출하는 것.

여기서 연산은 +, - * 만 허용된다.

그리고 연산을 완료한 후 절대값이 큰 값이 큰 수라고 정의한다.

---

문제를 풀기 위해

1. 연산의 우선순위 정하기
2. 연산 수식을 우선순위에 맞춰 후위 표현식으로 바꾸기
3. 연산하기

순 으로 문제를 풀었다.

1. 연산의 우선순위 정하기

	List<Character> oper = new ArrayList<>();
        if (expression.contains("+")) {
            oper.add('+');
        }
        if (expression.contains("-")) {
            oper.add('-');
        }
        if (expression.contains("*")) {
            oper.add('*');
        }

우선 연산 수식에 포함된 연산만을 찾아 List 에 추가했다

	opers = new char[oper.size()];
        for (int i = 0; i < opers.length; i++) {
            opers[i] = oper.get(i);
        }

List의 원소들을 character array 에 담아 dfs를 돌렸다.

static void simulation(int depth) {
        if (depth == opers.length) {
            long ret = calculate();
            answer = Math.max(ret, answer);
            return;
        }
        for (int i = depth; i < opers.length; i++) {
            swap(i, depth);
            simulation(depth + 1);
            swap(i, depth);
        }
    }

2. 연산 수식을 우선 순위에 맞춰 후위 표현식으로

	HashMap<String, Integer> hm = new HashMap<>();
        for (int i = 0; i < opers.length; i++) {
            hm.put(opers[i] + "", i);
        }
        StringBuilder sb = new StringBuilder();
        List<String> equation = new ArrayList<>();
        Stack<String> arg = new Stack<>();
        int len = exp.length();
        for (int i = 0; i < len; i++) {
            char c = exp.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                equation.add(sb.toString());
                sb.delete(0, sb.length());
                while (!arg.isEmpty() && hm.get(c+"") <= hm.get(arg.peek())) {
                    equation.add(arg.pop());
                }
                arg.push(c + "");
            } else {
                sb.append(c);
            }
        }
        equation.add(sb.toString());
        while (!arg.isEmpty()) {
            equation.add(arg.pop());
        }

우선 HashMap에 우선순위를 계산해 담아 두었다.

이후 수식의 길이가 최대 100이므로 전체 문자열을 검색하며 숫자는 삽입하고, 연산자는 우선 순위에 맞춰서 삽입했다.

StringBuilder는 숫자를 담았고, Stack은 연산자를, List는 후위 연산식을 담았다.

3. 연산

	Stack<Long> value = new Stack<>();
        for (String e : equation) {
            if (hm.containsKey(e)) {
                long b = value.pop();
                long a = value.pop();
                if (e.equals("+")) {
                    value.push(a + b);
                }
                if (e.equals("-")) {
                    value.push(a - b);
                }
                if (e.equals("*")) {
                    value.push(a * b);
                }
            } else {
                value.push(Long.parseLong(e));
            }
        }
        return Math.abs(value.pop());

List의 값을 가지고 전체 연산을 진행했다.

---

<전체 코드>

import java.util.*;

public class Solution {
    static char[] opers;
    static long answer;
    static String exp;

    public static long solution(String expression) {
        exp = expression;
        List<Character> oper = new ArrayList<>();
        if (expression.contains("+")) {
            oper.add('+');
        }
        if (expression.contains("-")) {
            oper.add('-');
        }
        if (expression.contains("*")) {
            oper.add('*');
        }
        opers = new char[oper.size()];
        for (int i = 0; i < opers.length; i++) {
            opers[i] = oper.get(i);
        }
        answer = -1;
        simulation(0);
        return answer;
    }

    static void simulation(int depth) {
        if (depth == opers.length) {
            long ret = calculate();
            answer = Math.max(ret, answer);
            return;
        }
        for (int i = depth; i < opers.length; i++) {
            swap(i, depth);
            simulation(depth + 1);
            swap(i, depth);
        }
    }

    static void swap(int i, int j) {
        char c = opers[i];
        opers[i] = opers[j];
        opers[j] = c;
    }

    static long calculate() {
        HashMap<String, Integer> hm = new HashMap<>();
        for (int i = 0; i < opers.length; i++) {
            hm.put(opers[i] + "", i);
        }
        StringBuilder sb = new StringBuilder();
        List<String> equation = new ArrayList<>();
        Stack<String> arg = new Stack<>();
        int len = exp.length();
        for (int i = 0; i < len; i++) {
            char c = exp.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                equation.add(sb.toString());
                sb.delete(0, sb.length());
                while (!arg.isEmpty() && hm.get(c+"") <= hm.get(arg.peek())) {
                    equation.add(arg.pop());
                }
                arg.push(c + "");
            } else {
                sb.append(c);
            }
        }
        equation.add(sb.toString());
        while (!arg.isEmpty()) {
            equation.add(arg.pop());
        }

        Stack<Long> value = new Stack<>();
        for (String e : equation) {
            if (hm.containsKey(e)) {
                long b = value.pop();
                long a = value.pop();
                if (e.equals("+")) {
                    value.push(a + b);
                }
                if (e.equals("-")) {
                    value.push(a - b);
                }
                if (e.equals("*")) {
                    value.push(a * b);
                }
            } else {
                value.push(Long.parseLong(e));
            }
        }
        return Math.abs(value.pop());
    }
}

Github Link