[Lv.2] 수식 최대화 : Java

프로그래머스

 

 

 

이해하기

처음 들었던 생각은 완전 탐색을 해야겠으니 dfs를 써야겠다. 이거 전에 풀었던 피로도 문제랑 비슷하게 풀면 되겠네~ 였다. (그리고 풀이 실패)

[Lv.2] 피로도 : Java

 

 

이번에 참고한 블로그는 아래!

[level2] 프로그래머스 - 수식 최대화(JAVA)

이 분의 풀이는 다음과 같다.

1. 연산자 순서를 전부 배열로 만들어둔다.
2. 문자열에서 숫자와 연산자를 분리하여 ArrayList에 추가
   1. 연산자를 만나면, 앞은 숫자이므로 먼저 추가
   2. 연산자 추가
   3. 1, 2번만 for문에서 수행하므로 마지막 숫자까지 추가!
3. 미리 만들어둔 연산자 우선순위 6개 경우에 대해 계산한다.
4. list에서 op[i][k]에 해당하는 수식을 만나면 자신의 앞의 숫자와 뒤의 숫자를 계산해준 후, 계산한 숫자로 앞의 숫자를 바꾼다. (자신과 다음 위치 숫자 제거)
5. 수식 계산이 끝나면 max 값 비교

import java.util.*;

class Solution {
static long answer = Long.MIN_VALUE;
    static String[][] op = {{"+", "-", "*"}, {"+", "*", "-"}, {"*", "+", "-"}, {"*", "-", "+"}, {"-", "*", "+"}, {"-", "+", "*"}};

    public long solution(String expression) {
        ArrayList<String> list = new ArrayList<>();
        int start = 0;
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*') {
                list.add(expression.substring(start, i));
                list.add(expression.charAt(i) + "");
                start = i + 1;
            }
        }

        list.add(expression.substring(start));

        for (int i = 0; i < op.length; i++) {
            ArrayList<String> subList = new ArrayList<>(list);
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < subList.size(); k++) {
                    if (op[i][j].equals(subList.get(k))) {
                        subList.set(k - 1, calc(subList.get(k - 1), subList.get(k), subList.get(k + 1)));
                        subList.remove(k);
                        subList.remove(k);
                        k--;
                    }
                }
            }
            answer = Math.max(answer, Math.abs(Long.parseLong(subList.get(0))));
        }

        return answer;
    }
    
    public String calc(String num1, String op, String num2) {
        long n1 = Long.parseLong(num1);
        long n2 = Long.parseLong(num2);

        if (op.equals("+")) {
            return n1 + n2 + "";
        } else if (op.equals("-")) {
            return n1 - n2 + "";
        } else {
            return n1 * n2 + "";
        }
    }
}

 

이 풀이를 보고 약간 당황했다.

아니 완탐은 완탐인데, dfs...? bfs? 이게 뭐지?? 라는 생각이 들었다.

다른 분들의 풀이도 많이 살펴보았지만 대부분 이런 방식으로 푸셨다.

요 풀이를 좀 더 응용해서 순열로 뽑아내는 걸 해보겠다.

 

 

문제풀이

    static long answer = Long.MIN_VALUE;
    static List<char[]> opList = new ArrayList<>();

    public long solution(String expression) {
        ArrayList<String> list = new ArrayList<>();
        int start = 0;
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*') {
                list.add(expression.substring(start, i));
                list.add(expression.charAt(i) + "");
                start = i + 1;
            }
        }
        list.add(expression.substring(start));

        char[] op = {'+', '-', '*'};
        perm(op, 0);

        for (int i = 0; i < opList.size(); i++) {
            ArrayList<String> subList = new ArrayList<>(list);
            char[] curOp = opList.get(i);
            for (int j = 0; j < curOp.length; j++) {
                for (int k = 0; k < subList.size(); k++) {
                    if ((curOp[j] + "").equals(subList.get(k))) {
                        subList.set(k - 1, calc(subList.get(k - 1), subList.get(k), subList.get(k + 1)));
                        subList.remove(k);
                        subList.remove(k);
                        k--;
                    }
                }
            }
            answer = Math.max(answer, Math.abs(Long.parseLong(subList.get(0))));
        }

        return answer;
    }

    public String calc(String num1, String op, String num2) {
        long n1 = Long.parseLong(num1);
        long n2 = Long.parseLong(num2);

        if (op.equals("+")) {
            return n1 + n2 + "";
        } else if (op.equals("-")) {
            return n1 - n2 + "";
        } else {
            return n1 * n2 + "";
        }
    }

    public void perm(char[] op, int depth) {
        if (depth == op.length) {
            char[] temp = op.clone();
            opList.add(temp);
            return;
        }

        for (int i = depth; i < op.length; i++) {
            swap(op, depth, i);
            perm(op, depth + 1);
            swap(op, depth, i);
        }
    }

    public void swap(char[] op, int depth, int i) {
        char temp = op[depth];
        op[depth] = op[i];
        op[i] = temp;
    }

 

시간은 전의 풀이보다 오래 걸리지만 연산자 개수가 바뀌는 경우를 위해서는 이렇게 푸는게 더 나을지도...

하여튼 힘들닷...^^