Java - [프로그래머스 Lv.2]67257 - 수식 최대화

출처

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

문제

세가지의 연산자중 우선순위를 다르게 하여, 연산결과의 합이 가장 큰 값을 구하는 문제입니다.

풀이

우선 필요한 연산을 하나씩 단계별로 진행해야 합니다.

첫번째로, 문자열로 주어지는 연산식을 숫자와 연산자로 분리해야 합니다. 저는 두개의 리스트로 분리하였습니다.

	int idx = 0;
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*') {
                opList.add(ch);
                numList.add(Long.parseLong(expression.substring(idx, i)));
                idx = i + 1;
            }
        }
        numList.add(Long.parseLong(expression.substring(idx)));

이제 주어진 연산자의 갯수에 맞추어 우선순위의 조합을 구해주어야 합니다. 저는 우선순위의 조합을 구하기 위해 DFS를 사용하였습니다.

public void dfs(String[] tmp, int n) {
        if (n == operatorNum) {
            answer = Math.max(calcurate(tmp), answer);
            return ;
        }
        for (int i = 0; i < operatorNum; i++) {
            if (!visited[i]) {
                visited[i] = true;
                tmp[n] = existOperators.get(i);
                dfs(tmp, n+1);
                visited[i] = false;
                tmp[n] = null;
            }
        }
        
    }

visited 배열을 통해 방문 여부를 선택해주고, tmp배열에 n을 통해 우선순위 순서대로 조합을 구해주었습니다. (0번 인덱스에 있는 연산자가 우선순위가 제일 높음)

이제 조합이 완성될 때 마다, calcurate()함수를 호출해주어 연산자 우선순위에 따라 계산을 진행하여 Math.max를 이용, 큰 값을 answer에 저장해줍니다.

public long calcurate(String[] tmp) {
        List<Long> numListtmp = new ArrayList<>(numList);
        List<String> opListtmp = new ArrayList<>(opList);

        int now_op = 0;
        while (!opListtmp.isEmpty()) {
            if (opListtmp.contains(tmp[now_op])) {
                for (int i = 0; i < opListtmp.size(); i++) {
                    if (opListtmp.get(i).equals(tmp[now_op])) {
                        numListtmp.add(i, 
                        calc(numListtmp.remove(i), numListtmp.remove(i), opListtmp.remove(i)));
                        break;
                    }
                }
            } else {
                now_op++;
            }

        }
        return numListtmp.get(0);
    }

연산에서 사용할 숫자열과 연산자의 리스트의 복사본을 만들어줍니다. 연산자의 리스트인 opListtmp가 비어있을 때 까지 반복합니다. 우선순위에 따른 연산자가 존재한다면, 숫자와 연산자를 리스트와 숫자를 그 remove 하여 결과 값을 받아오고, 그 결과를 다시 숫자 리스트의 기존 위치에 add 하여 줍니다.

아래는 전체 코드입니다.

전체 코드

import java.util.*;
import java.math.*;

class Solution {

    String[] operator = {"+", "*", "-"};
    List<String> existOperators = new ArrayList<>();
    boolean visited[];
    long answer = 0;
    int operatorNum = 0;
    List<Long> numList = new ArrayList<>();
    List<String> opList = new ArrayList<>();


    public long solution(String expression) {
        int idx = 0;
        // 연산식을 List로 분리하기
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*') {
                opList.add(ch);
                numList.add(Long.parseLong(expression.substring(idx, i)));
                idx = i + 1;
            }
        }
        numList.add(Long.parseLong(expression.substring(idx)));


        for (int i = 0; i < operator.length; i++) {
            if (expression.contains(operator[i])) {
                existOperators.add(operator[i]);
            }
        }
        operatorNum = existOperators.size();
        visited = new boolean[operatorNum];
        dfs(new String[operatorNum], 0);


        return answer;
    }

    public void dfs(String[] tmp, int n) {
        if (n == operatorNum) {
            answer = Math.max(calcurate(tmp), answer);
            return ;
        }
        for (int i = 0; i < operatorNum; i++) {
            if (!visited[i]) {
                visited[i] = true;
                tmp[n] = existOperators.get(i);
                dfs(tmp, n+1);
                visited[i] = false;
                tmp[n] = null;
            }
        }
        
    }

    public long calcurate(String[] tmp) {
        List<Long> numListtmp = new ArrayList<>(numList);
        List<String> opListtmp = new ArrayList<>(opList);

        int now_op = 0;
        while (!opListtmp.isEmpty()) {
            if (opListtmp.contains(tmp[now_op])) {
                for (int i = 0; i < opListtmp.size(); i++) {
                    if (opListtmp.get(i).equals(tmp[now_op])) {
                        numListtmp.add(i, 
                        calc(numListtmp.remove(i), numListtmp.remove(i), opListtmp.remove(i)));
                        break;
                    }
                }
            } else {
                now_op++;
            }

        }
        return numListtmp.get(0);
    }

    private long calc(long num1, long num2, String op) {
        long tmp;
        if (op.equals("+")) {
            ret = num1 + num2;
        } else if (op.equals("-")) {
            ret = num1 - num2;
        } else {
            ret = num1 * num2;
        }
        return tmp;
    }

}