[프로그래머스] 수식 최대화(Java/자바) || 2020카카오인턴십 - dfs, 순열

문제

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

프로그래머스

문제 요약

연산자 우선순위를 재정의 하여 주어진 수식을 계산.

재정의 된 우선순위를 가지고 계산한 값 중 가장 큰 값 리턴

 

 

풀이

0. expression에서 연산자와 숫자 분리

        String number = "";
        numList = new ArrayList<>();
        operList = new ArrayList<>();
        
        for(int i=0; i<expression.length(); i++){
            char now = expression.charAt(i);
            if(now=='-' || now=='+' || now=='*'){
                operList.add(now);
                numList.add(Long.parseLong(number));
                number = "";
            }else{
                number+=now;
            }
        } // 분리
        numList.add(Long.parseLong(number));

 

1. 연산자의 순열을 구함

- 연산자가 +, -, * 3가지만 존재하므로, 미리 구해서 계산해도 되지만 dfs로 순열을 구해서 계산

    public static void dfs(int cnt){
        if(cnt == 3){
            long temp = solve();
            if(answer<temp) answer = temp;
            return;
        }
        
        for(int i=0; i<3; i++){
            if(visit[i]==1) continue;
            operSelect[cnt] = operation[i];
            visit[i] = 1;
            dfs(cnt+1);
            visit[i] = 0;
        }
    }

 

2. 해당 우선순위로 주어진 수식 계산

- ArrayList로 계산 (주석 참조)

    public static long solve(){
        long result = 0;
        ArrayList<Character> oper = new ArrayList<>(operList); // 원래의 값 보존을 위해 복사
        ArrayList<Long> num = new ArrayList<>(numList); // 원래의 값 보전을 위해 복사
        
        for(int i=0; i<3; i++){
            char nowOper = operSelect[i];
            
            for(int idx = 0; idx<oper.size(); idx++){
                if(oper.get(idx)==nowOper){
                    long a = num.get(idx);
                    long b = num.get(idx+1);
                    result = calc(a, b, nowOper);
                    
                    // 계산하였으니 해당 위치에 숫자 갱신
                    num.remove(idx+1); // 두번째 값은 remove
                    num.set(idx, result); // 앞에 값은 계산한 값을 set
                    oper.remove(idx); // operation 삭제
                    
                    idx--; // idx위치의 연산자 삭제했으니 index-1
                }
            }
        }
        return Math.abs(result); // 절댓값 리턴
    }

 

전체 코드

import java.util.*;
class Solution {
    static ArrayList<Long> numList;
    static ArrayList<Character> operList;
    static int visit[];
    static char[] operation = {'-', '+', '*'};
    static char[] operSelect;
    static long answer;
    
    public long solution(String expression) {
        answer = 0;
        String number = "";
        numList = new ArrayList<>();
        operList = new ArrayList<>();
        
        for(int i=0; i<expression.length(); i++){
            char now = expression.charAt(i);
            if(now=='-' || now=='+' || now=='*'){
                operList.add(now);
                numList.add(Long.parseLong(number));
                number = "";
            }else{
                number+=now;
            }
        } // 분리
        numList.add(Long.parseLong(number));
        
        // 연산자 우선순위와 연산
        operSelect = new char[3];
        visit = new int[3];
        dfs(0);
        
        return answer;
    }
    
    public static void dfs(int cnt){
        if(cnt == 3){
            long temp = solve();
            if(answer<temp) answer = temp;
            return;
        }
        
        for(int i=0; i<3; i++){
            if(visit[i]==1) continue;
            operSelect[cnt] = operation[i];
            visit[i] = 1;
            dfs(cnt+1);
            visit[i] = 0;
        }
    }
    
    public static long solve(){
        long result = 0;
        ArrayList<Character> oper = new ArrayList<>(operList);
        ArrayList<Long> num = new ArrayList<>(numList);
        
        for(int i=0; i<3; i++){
            char nowOper = operSelect[i];
            
            for(int idx = 0; idx<oper.size(); idx++){
                if(oper.get(idx)==nowOper){
                    long a = num.get(idx);
                    long b = num.get(idx+1);
                    result = calc(a, b, nowOper);
                    
                    num.remove(idx+1);
                    num.set(idx, result);
                    oper.remove(idx);
                    
                    idx--;
                }
            }
        }
        return Math.abs(result);
    }
    
    public static long calc(long a, long b, char c){
        switch(c){
            case '-':
                return a-b;
            case '+':
                return a+b;
            default:
                return a*b;
        }
    }
}