[코딩테스트][프로그래머스] 수식 최대화

문제

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

python

from itertools import permutations
from collections import deque
import copy

def solution(expression):
    answer = 0
    
    oper=['+','-','*']
    
    oper_prior=list(permutations(oper,3))
    
    exp_list=list(expression)
    num_str=''
    exp_main=[]
    for i in exp_list:
        if i not in oper:
            num_str+=i
        else:
            exp_main.append(num_str)
            exp_main.append(i)
            num_str=''
    if num_str!='':
        exp_main.append(num_str)
    max_value=0
    for prior in oper_prior:
        exp=copy.deepcopy(exp_main)
        for op in prior:
            new_arr=[]
            k=0
            while k<len(exp):
                if exp[k] == op:
                    mid=eval(new_arr[-1]+exp[k]+exp[k+1])
                    new_arr[-1]=str(mid)
                    k+=2
                else:
                    new_arr.append(exp[k])
                    k+=1
            exp=new_arr
        max_value=max(max_value,abs(int(exp[0])))
    answer=max_value
    
    return answer

java

import java.util.*;

class Solution {
    public static List<String[]> generatePermutations(String[] strArray){
        List<String[]> permutations = new ArrayList<>();
        generatePermutations(new ArrayList<>(),List.of(strArray),permutations);
        return permutations;
    }
    private static void generatePermutations(List<String> prefix, List<String> strList, List<String[]> permutations){
        int n=strList.size();
        if(n==0){
            permutations.add(prefix.toArray(new String[0]));
        }else{
            for(int i=0;i<n;i++){
                List<String> newPrefix = new ArrayList<>(prefix);
                newPrefix.add(strList.get(i));
                List<String> remaining = new ArrayList<>(strList.subList(0,i));
                remaining.addAll(strList.subList(i+1,n));
                generatePermutations(newPrefix,remaining,permutations);
            }
        }
    }
    public long solution(String expression) {
        long answer = 0;
        
        String[] opers=new String[]{"+","-","*"};
        List<String[]> oper_prior_list=generatePermutations(opers);
        String[] exp_list=expression.split("");
        
        StringBuilder num_str=new StringBuilder();
        List<String> exp_main=new ArrayList<>();
        for(int i=0;i<exp_list.length;i++){
            if(Arrays.asList(opers).contains(exp_list[i])){
                exp_main.add(num_str.toString());
                exp_main.add(exp_list[i]);
                num_str=new StringBuilder();
            }else{
                num_str.append(exp_list[i]);
            }
        }
        if(num_str.length()!=0){
            exp_main.add(num_str.toString());
        }
        long max_value=0;
        for(String[] prior:oper_prior_list){
            List<String> exp=new ArrayList<>(exp_main);
            for(String op:prior){
                List<String> new_arr=new ArrayList<>();
                int k=0;
                while(k<exp.size()){
                    if(exp.get(k).equals(op)){
                        long first=Long.parseLong(new_arr.get(new_arr.size()-1));
                        String oper_this=exp.get(k);
                        long second=Long.parseLong(exp.get(k+1));
                        long mid=0;
                        if(oper_this.equals("+")){
                            mid=first+second;
                        }else if(oper_this.equals("*")){
                            mid=first*second;
                        }else{
                            mid=first-second;
                        }
                        new_arr.set(new_arr.size()-1,Long.toString(mid));
                        k+=2;
                    }else{
                        new_arr.add(exp.get(k));
                        k+=1;
                    }
                }
                exp=new_arr;
            }
            max_value=Math.max(max_value,Math.abs(Long.parseLong(exp.get(0))));
        }
        answer=max_value;
        return answer;
    }
}

내 생각

• python 풀이시간 : 60분
• java 풀이시간 : 60분
• python에서 자바 코드로 바꾸는데만 하루종일...
• 입력받은 수식을 숫자와 operater로 분리시켜 리스트에 저장해둔다. 그리고 3개의 연산자를 순열을 통해 모든 케이스를 추린다. 각 케이스를 반복문을 통해 돌리면서 이중 반복문을 통해 하나씩 꺼내다가 operater를 꺼냈을 때, 직전에 넣은 숫자와 다음에 나올 숫자를 하나 받아서 해당 연산자로 계산한다. 연산자가 아닌 숫자인 경우에는 그냥 리스트에 담는다. 그렇게 해당 연산자로 수식을 하고 다음연산자가 수행되는 식으로 우선순위를 케이스에 따라 계산한다. 각 케이스마다 연산값을 최댓값과의 비교를 통해 갱신하는 형태로 답을 구한다.