(2020카카오) 수식최대화 Java

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

문제를 잘 읽자 백만번 제창하기

: 덧셈,뺄셈,곱셈,나눗셈 인줄 알고 경우의 수가 4!인줄알고 permutation(순열)을 고민했다. 그랬다면 Level3 문제였겠지. 덧셈,뺄셈,곱셈 세가지의 경우에만 해당하므로 3!=6가지 뿐이므로 순열부분을 수작업으로 처리했다.

 

그리고 만약 나눗셈까지 있었다면 고려해야될 예외사항이 많이 나와서 아마 문제에서 나눗셈은 뺀것같다.

ex) 나누는값이 0인경우와 같은 상황.

 

<참고>

 

stack 복사

Stack<String> stack = new Stack<>();

Stack<String> t = (Stack<String>) stack.clone();

t = stack; 이런식으로는 복사가 안된다. 따라서 반복문으로는 pop을 해야되므로 옮기기 힘드니깐 굳이 그러지말고 clone() 메소드를 이용하는것을 추천한다.

 

---

풀이

 

중위연산자를 계산하는방법에 대해 생각해보자.

Stack이 가장 먼저 떠오를 것이다. 직관적으로 코드를 짜보려고 노력했다.

 

1. 연산자 및 숫자 추출해서 차례대로 stack에 String형으로 집어넣는다.

 

=> 이때 연산자만 추출해야할때 처음에 사용했던 방법을 참고하라고 적어놓는다. (특수문자 인식 관련)

 expression.split("\\*|\\+|-");
 /*
 문자열을 분리하는 방법 : split 메소드에서 
 
 여러개의 문자를 기준으로 자르고싶을때는 | 를 사용한다.
 
 그리고 특수문자 인식은 위처럼 \\를 붙여준다.
 
 */

어째서인지 \\*을 해도 인식이 되긴한다. 하지만 아래 글을 참고해보니 정확한것은 [*]이 맞나보다.

jobc.tistory.com/87

[Java] String 클래스에서 특수문자 인식

 

 

 

2. 추출한 것을 담은 스택을 각각의 순열방식대로 탐색하여 max값을 추출한다.

 

 

 

3. 탐색은 +,-,* 모두 방식은 같으며,

Stack에서 pop하다가 특수문자를 pop한 경우 이전값과 다음값을 계산해주어서 다시 stack에 넣어주는 방식이다.

 

(단, 끝까지 탐색한경우 Stack EmptyException을 대비하여 size>=2일때까지 해당 작업을 계속하는것으로 반복했다. 어차피 마지막 stack의 값은 숫자이기 때문이다.)

 

 

 

전체코드

import java.util.*;

class Solution {
    public long solution(String expression) {
        long answer = 0;
        Stack<String> stack = new Stack<>();

        int sslength = expression.length() - 1;
        String s = "";
        for (int i = expression.length() - 1; i >= 0; i--) {
            if (expression.charAt(i) == '*' || expression.charAt(i) == '/' || expression.charAt(i) == '+' || expression.charAt(i) == '-') {
                stack.push(s);
                stack.push(String.valueOf(expression.charAt(i)));
                s = "";
            } else {
                s = expression.charAt(i) + s;
            }
        }
        stack.push(s);

        //경우의수 순열 해야됨.
        ArrayList<Long> q = new ArrayList<>();

        Stack<String> t = (Stack<String>) stack.clone();
        Plus(t);
        Minus(t);
        Mult(t);
        q.add(Math.abs(Long.parseLong(t.pop())));

        t = (Stack<String>) stack.clone();
        Plus(t);
        Mult(t);
        Minus(t);
        q.add(Math.abs(Long.parseLong(t.pop())));

        t = (Stack<String>) stack.clone();
        Minus(t);
        Plus(t);
        Mult(t);
        q.add(Math.abs(Long.parseLong(t.pop())));

        t = (Stack<String>) stack.clone();
        Minus(t);
        Mult(t);
        Plus(t);
        q.add(Math.abs(Long.parseLong(t.pop())));

        t = (Stack<String>) stack.clone();
        Mult(t);
        Plus(t);
        Minus(t);
        q.add(Math.abs(Long.parseLong(t.pop())));

        t = (Stack<String>) stack.clone();
        Mult(t);
        Minus(t);
        Plus(t);
        q.add(Math.abs(Long.parseLong(t.pop())));


        answer = Collections.max(q);
        return answer;
    }


    public static void Plus(Stack<String> stack) {
        Stack<String> temp = new Stack<>();

        while (!stack.isEmpty()) {
            if (stack.size() >= 2) {
                String left = stack.pop();
                String mid = stack.pop();

                if (mid.equals("+")) {
                    long val = Long.parseLong(left) + Long.parseLong(stack.pop());
                    stack.push(Long.toString(val));//queue에 넣어야 순서가 유지됨
                } else {
                    temp.push(left);
                    temp.push(mid);
                }
            } else {
                while (!stack.isEmpty()) {
                    temp.push(stack.pop());
                }
            }
        }
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }

    public static void Minus(Stack<String> stack) {
        Stack<String> temp = new Stack<>();

        while (!stack.isEmpty()) {
            if (stack.size() >= 2) {
                String left = stack.pop();
                String mid = stack.pop();

                if (mid.equals("-")) {
                    long val = Long.parseLong(left) - Long.parseLong(stack.pop());
                    stack.push(Long.toString(val));//queue에 넣어야 순서가 유지됨
                } else {
                    temp.push(left);
                    temp.push(mid);
                }
            } else {
                while (!stack.isEmpty()) {
                    temp.push(stack.pop());
                }
            }
        }
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }public static void Mult(Stack<String> stack) {
        Stack<String> temp = new Stack<>();

        while (!stack.isEmpty()) {
            if (stack.size() >= 2) {
                String left = stack.pop();
                String mid = stack.pop();

                if (mid.equals("*")) {
                    long val = Long.parseLong(left) * Long.parseLong(stack.pop());
                    stack.push(Long.toString(val));//queue에 넣어야 순서가 유지됨
                } else {
                    temp.push(left);
                    temp.push(mid);
                }
            } else {
                while (!stack.isEmpty()) {
                    temp.push(stack.pop());
                }
            }
        }
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }
}