2020 카카오 인턴십 수식 최대화 level 2 - java

 

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

이 문제는 사실 +, -, *의 우선순위에 따라 최대값을 구하는 문제여서 6개의 경우의수를 모두 구해서 최대값을 리턴해주었다.

이 문제는 다른 문제가 좀 더 레퍼런스로 좋을 것 같다!

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    long answer = Integer.MIN_VALUE;
    public long solution(String expression) {
        answer = Math.max(answer,minusMulPlus(expression));
        answer = Math.max(answer,minusPlusMul(expression));
        answer = Math.max(answer,mulPlusMinus(expression));
        answer = Math.max(answer,mulMinusPlus(expression));
        answer = Math.max(answer,plusMulMinus(expression));
        answer = Math.max(answer,plusMinusMul(expression));

        System.out.println(answer);
        return answer;
    }
    private long minusPlusMul(String expression) {
        String[] numberStringArr = expression.split("[-*+]");
        Deque<String> queue = new LinkedList<>();
        String[] signArr = expression.replaceAll("[0-9]", "").split("");

        // expression 초기화
        for(int i = 0 ;i<signArr.length;i++) {
            queue.add(numberStringArr[i]);
            queue.add(signArr[i]);
        }
        queue.add(numberStringArr[signArr.length]);

        Deque<String> firstMinus = minus(queue);

        // - > + > *
        Deque<String> MinusPlusMul = plus(firstMinus);
        MinusPlusMul = multiply(MinusPlusMul);
        long aa = Long.valueOf(MinusPlusMul.poll());
        if(Math.abs(aa) > answer){
            answer = Math.abs(aa);
        }
        return answer;

    }

    private long minusMulPlus(String expression) {
        String[] numberStringArr = expression.split("[-*+]");
        Deque<String> queue = new LinkedList<>();
        String[] signArr = expression.replaceAll("[0-9]", "").split("");

        // expression 초기화
        for(int i = 0 ;i<signArr.length;i++) {
            queue.add(numberStringArr[i]);
            queue.add(signArr[i]);
        }
        queue.add(numberStringArr[signArr.length]);

        Deque<String> firstMinus = minus(queue);

        // - > * > +
        Deque<String> MinusMulPlus = multiply(firstMinus);
        MinusMulPlus = plus(MinusMulPlus);
        long aa = Long.valueOf(MinusMulPlus.poll());
        if(Math.abs(aa) > answer){
            answer = Math.abs(aa);
        }

        return answer;

    }

    private long mulPlusMinus(String expression) {
        String[] numberStringArr = expression.split("[-*+]");
        Deque<String> queue = new LinkedList<>();
        String[] signArr = expression.replaceAll("[0-9]", "").split("");

        // expression 초기화
        for(int i = 0 ;i<signArr.length;i++) {
            queue.add(numberStringArr[i]);
            queue.add(signArr[i]);
        }
        queue.add(numberStringArr[signArr.length]);

        Deque<String> firstMul = multiply(queue);

        // * > + > -
        Deque<String> MulPlusMinus = plus(firstMul);
        MulPlusMinus = minus(MulPlusMinus);
        long aa = Long.valueOf(MulPlusMinus.poll());
        if(Math.abs(aa) > answer){
            answer = Math.abs(aa);
        }
        return answer;
    }

    private long mulMinusPlus(String expression) {
        String[] numberStringArr = expression.split("[-*+]");
        Deque<String> queue = new LinkedList<>();
        String[] signArr = expression.replaceAll("[0-9]", "").split("");

        // expression 초기화
        for(int i = 0 ;i<signArr.length;i++) {
            queue.add(numberStringArr[i]);
            queue.add(signArr[i]);
        }
        queue.add(numberStringArr[signArr.length]);

        Deque<String> firstMul = multiply(queue);

        // * > - > +
        Deque<String> MulMinusPlus = minus(firstMul);
        MulMinusPlus = plus(MulMinusPlus);
        long aa = Long.valueOf(MulMinusPlus.poll());
        if(Math.abs(aa) > answer){
            answer = Math.abs(aa);
        }
        return answer;

    }

    private long plusMulMinus(String expression) {
        String[] numberStringArr = expression.split("[-*+]");
        Deque<String> queue = new LinkedList<>();
        String[] signArr = expression.replaceAll("[0-9]", "").split("");

        // expression 초기화
        for(int i = 0 ;i<signArr.length;i++) {
            queue.add(numberStringArr[i]);
            queue.add(signArr[i]);
        }
        queue.add(numberStringArr[signArr.length]);

        Deque<String> firstPlus = plus(queue);

        // + > * > -
        Deque<String> PlusMulMinus = multiply(firstPlus);
        PlusMulMinus = minus(PlusMulMinus);
        long aa = Long.valueOf(PlusMulMinus.poll());
        if(Math.abs(aa) > answer){
            answer = Math.abs(aa);
        }
        return answer;

    }

    private long plusMinusMul(String expression) {
        String[] numberStringArr = expression.split("[-*+]");
        Deque<String> queue = new LinkedList<>();
        String[] signArr = expression.replaceAll("[0-9]", "").split("");

        // expression 초기화
        for(int i = 0 ;i<signArr.length;i++) {
            queue.add(numberStringArr[i]);
            queue.add(signArr[i]);
        }
        queue.add(numberStringArr[signArr.length]);

        Deque<String> firstPlus = plus(queue);

        // + > - > *
        Deque<String> PlusMinusMul = minus(firstPlus);
        PlusMinusMul = multiply(PlusMinusMul);
        long aa = Long.valueOf(PlusMinusMul.poll());
        if(Math.abs(aa) > answer){
            answer = Math.abs(aa);
        }
        return answer;

    }

    private Deque<String> multiply(Deque<String> queue) {
        Deque<String> answer = new LinkedList<>();
        String peek;
        while(!queue.isEmpty()) {
            String element =queue.poll();
            if(element.equals("*")) {
                long a = Long.valueOf(answer.pollLast());
                long b = Long.valueOf(queue.poll());
                peek = String.valueOf(a*b);
            } else {
                peek = element;
            }
            answer.add(peek);
        }
        return answer;
    }

    private Deque<String> plus(Deque<String> queue) {
        Deque<String> answer = new LinkedList<>();
        String peek;
        while(!queue.isEmpty()) {
            String element =queue.poll();
            if(element.equals("+")) {
                long a = Long.valueOf(answer.pollLast());
                long b = Long.valueOf(queue.poll());
                peek = String.valueOf(a+b);
            } else {
                peek = element;
            }
            answer.add(peek);
        }
        return answer;
    }

    private Deque<String> minus(Deque<String> queue) {
        Deque<String> answer = new LinkedList<>();
        String peek;
        while(!queue.isEmpty()) {
            String element =queue.poll();
            if(element.equals("-")) {
                long a = Long.valueOf(answer.pollLast());
                long b = Long.valueOf(queue.poll());
                peek = String.valueOf(a-b);
            } else {
                peek = element;
            }
            answer.add(peek);
        }
        return answer;
    }

}

public class code {
    public static void main(String[] args) {
        Solution s = new Solution();
        String str = "100-200*300-500+20";
        s.solution(str);
    }
}