[Java] 프로그래머스 - 수식 최대화

[문제]

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

코딩테스트 연습 - 수식 최대화

[풀이]

조합과 백트래킹을 이용하여 풀이하였습니다.

 

우선 필요한 자료들을 세팅합니다.

• ArrayList<String> exp로 중복을 제거하며 연산자를 넣어주었습니다.
  • (Set 자료형을 이용하면 편리하지만, 풀이 당시에는 생각을 못했습니다.ㅎㅎ)
• expression.charAt(i) < 48를 통해 연산자를 구분하였습니다.
  • ( 아스키 코드 이용 )
• 연산자들은 numbers에 " "으로 구분하여 저장하고, 숫자들은 operator에 저장하였습니다.
  • 연산자 : “*+-” , 숫자 : “10 20 300”

다음으로 setNumber()를 통해 풀이를 진행하였습니다.

• 연산자들의 우선순위가 되는 순서쌍을 구해서 calcuate()를 통해 해당 연산자를 모두 수행시켜 계산한 결과를 numbers에 저장하고 operator에 계산한 연산자 외의 연산자들을 새로 저장하여 setNumber() 재귀를 통해 모두 연산시켰습니다.

 

 

[코드]

import java.util.*;
class Solution {
    static ArrayList<String> exp = new ArrayList<String>();
    static long max = Long.MIN_VALUE;
    public long solution(String expression) {
        long answer = 0;
        StringBuffer sb = new StringBuffer();
        sb.append(expression);
        
        String operator = "";

        for(int i=0;i<expression.length();i++) {
            if(expression.charAt(i) < 48) {
                String s = "" + expression.charAt(i);
                operator += s;
                if(!exp.contains(s)) {
                    exp.add(s);
                }
                sb.replace(i, i+1, " ");
            }
        }
        String numbers = sb.toString();    
        boolean[] visit = new boolean[exp.size()];
        setNumber("", visit, 0, numbers, operator);
        answer = max;
        return answer;
    }
    // 순서쌍 구하기
    public static void setNumber(String str, boolean[] visit, int cnt, String numbers, String operator) {
        if(cnt >= exp.size()) {
            Long absNum = Math.abs(Long.parseLong(numbers));
            if(max < absNum) {
                max = absNum;
            }
            return;
        }
        for(int i=0;i<exp.size();i++) {
            if(!visit[i]) {
                visit[i] = true;
                String[] nums = numbers.split(" ");
                String[] opers = operator.split("");
                
                String newNums = "";
                String newOpers = "";
                for(int j=0;j<nums.length-1;j++) {
                    if(opers[j].equals(exp.get(i))) {
                        String n = calculate(nums[j], nums[j+1], opers[j]);
                        nums[j+1] = n;
                    } else {
                        newNums = newNums + nums[j] + " ";
                        newOpers += opers[j];
                    }
                }
                newNums = newNums + nums[nums.length-1];
                setNumber(str + exp.get(i), visit, cnt+1, newNums, newOpers);
                visit[i] = false;
            }
        }
    }
    public static String calculate(String a, String b, String o) {
        long result = 0L;
        if(o.equals("+")) {
            result = Long.parseLong(a) + Long.parseLong(b);
        } else if(o.equals("-")) {
            result = Long.parseLong(a) - Long.parseLong(b);
        } else if(o.equals("*")) {
            result = Long.parseLong(a) * Long.parseLong(b);
        } else {
            result = Long.parseLong(a) / Long.parseLong(b);
        }
        return Long.toString(result);
    }
}