프로그래머스 LV2. 수식 최대화 (자바)

🍀 문제해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

• expression은 길이가 3 이상 100 이하인 문자열입니다.
• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력 예

expression	result
"100-200*300-500+20"	60420
"50*6-3*2"	300

 

 

 

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

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

 

😊 나의 코드

import java.util.*;
class Solution {
    ArrayList<String> arr = new ArrayList<>();
    long max = 0;
    public long solution(String expression) {
        long answer = 0;
        long num = 0;

        String susicStr = "";
        if(expression.indexOf('-')>0) susicStr+="- ";
        if(expression.indexOf('+')>0) susicStr+="+ ";
        if(expression.indexOf('*')>0) susicStr+="* ";
        String[] susic = susicStr.split(" ");

        String ex = "";
        for (int i = 0; i < expression.length(); i++) {
            char e = expression.charAt(i);
            if (e == '-' || e == '*' || e == '+') {
                arr.add(ex);
                arr.add("" + e);
                ex = "";
            } else {
                ex += e;
            }
        }
        arr.add(ex);

        String[] output = new String[susic.length];
        boolean[] visited = new boolean[susic.length];
        perm(susic, output, visited, 0, susic.length);
        return max;
    }

    public long calculate(long n1, long n2, String susic) {
        if(susic.equals("-")) {
            return n1-n2;
        }else if(susic.equals("+")) {
            return n1+n2;
        }else {
            return n1*n2;
        }
    }

    public long calculate2(ArrayList<String> copiedArr,String[] susic) {
        int susicIndex = 0;
        while(copiedArr.size()>1) {
            for(int i=0; i<copiedArr.size();i++) {
                if(copiedArr.get(i).equals(susic[susicIndex])) {
                    long cal = calculate(Long.parseLong(copiedArr.get(i-1)), Long.parseLong(copiedArr.get(i+1)), copiedArr.get(i));
                    copiedArr.set(i-1, Long.toString(cal));
                    copiedArr.remove(i+1);
                    copiedArr.remove(i);
                    i--;
                }
            }
            susicIndex++;
        }
        return Long.parseLong(copiedArr.get(0));
    }

    public void perm(String[] susic, String[] output, boolean[] visited, int depth, int n) {
        if (depth == n) {
            ArrayList<String> copiedArr = new ArrayList<>();
            copiedArr.addAll(arr);
            long cal = Math.abs(calculate2(copiedArr,output));
            if(cal>max) {
                max = cal;
            }
            return;
        }

        for (int i=0; i<n; i++) {
            if (visited[i] != true) {
                visited[i] = true;
                output[depth] = susic[i];
                perm(susic, output, visited, depth + 1, n);
                visited[i] = false;
            }
        }
    }
}

 

1. 수식에 나온 연산 susic[] 배열에 담기

2. 수식에 나온 숫자/연산 arr 리스트에 담기

3. perm 메소드로 연산의 우선순위 순열 구하기

4. caculate2 메소드로 우선순위에 따른 결과 계산하여 리턴

5. max 값과 비교하여 제일 큰 결과값 저장하여 리턴