[프로그래머스][Level2][JAVA] 수식 최대화

[문제 설명]

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

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

 

[풀이 과정]

문제를 해결하는데에 3가지 알고리즘 및 자료구조 지식을 이용했다. 

1. 순열

2. 수식의 계산 - 중위표기법, 후위표기법

3. 스택 

(2를 계산할 때 3이 사용된다.)

 

1. 순열

문제에서는 +, -, * 이 세가지 연산자의 우선순위를 자유롭게 재정의 하여 가장 큰 답을 만드는 계산식의 결과를 리턴하라고 한다. 

+, -, * 의 우선순위를 모두 만들어봐야 어떤 우선순위가 가장 큰 답을 만드는지 알 수 있다. 

아이템의 중복을 허용하지 않으며 순서를 고려하는 나열법이므로 순열을 이용하여 경우의 수를 모두 구할 수 있다. 

public static void permutation(int[] items, int[] buckets, int k) {
        if (k == 0) {
            // 경우의 수로 하고자 하는 로직을 실행 
            return;
        }

        int lastIndex = buckets.length - k - 1;
        for (int i = 0; i < items.length; i++) {
            boolean flag = true;

            for (int j = 0; j <= lastIndex; j++) {
                if (buckets[j] == items[i]) {
                    flag = false;
                }
            }

            if (flag) {
                buckets[lastIndex + 1] = items[i];
                permutation(items, buckets, k - 1);
            }
        }
    }

 

 

2. 수식의 계산 - 중위표기법, 후위표기법
3. 스택

후위표기법의 특징은 수식에 괄호가 없어도 우선순위가 반영되어 있다. 

즉, 문제에 나온 중위표기법을 적용하고 자는 우선순위가 반영된 후위표기법으로 만들 수 있다.  

적용하고자 하는 우선순위는 순열에서 구한 경우의 수들이다. 각 경우에 수에 대응하는 후위표기법을 만든다. 

중위표기법 및 후위표기법 계산에는 자료구조 스택을 사용한다. 

/**
     * 중위 표기법 -> 후위 표기법으로 변환
     * @param postfix
     * @param priorities
     * @return
     */
    public static String[] postfixToInfix(String postfix, int[] priorities) {
        // String을 배열로 변환
        String[] postfixArray = strToArray(postfix);
        String[] infixArray = new String[postfixArray.length];
        String[] op = {"+", "-", "*"};
        Stack<String> stack = new Stack<>();
        int index = 0;

        for (int i = 0; i < postfixArray.length; i++) {
            // 배열의 원소가 연산자이면
            if (Arrays.asList(op).contains(postfixArray[i])) {
                // 스택이 비어있으면
                if (stack.isEmpty()) {
                    // 연산자를 push
                    stack.push(postfixArray[i]);
                } else {
                    // 스택이 비어있지 않다면
                    // 스택에 먼저 들어있는 연산자들이 현재 연산자보다 우선순위가 높다면 pop
                    while (!stack.isEmpty() && compareToOperation(postfixArray[i], stack.peek(), priorities)) {
                        // 후위표기법 계산식에 스택에서 pop한 연산자 출력
                        infixArray[index++] = stack.pop();
                    }
                    // 현재 연산자를 스택에 push
                    stack.push(postfixArray[i]);
                }
            // 피연산자이면 후위표기법 계산식에 바로 출력
            } else {
                infixArray[index++] = postfixArray[i];
            }
        }

        // 스택에 남아있던 연산자들 모두 후위표기법 계산식에 pop하여 출력
        while (!stack.isEmpty()) {
            infixArray[index++] = stack.pop();
        }

        return infixArray;
    }

    public static String[] strToArray(String postfix) {
        String[] numStrArray = postfix.replaceAll("[^0-9]", " ").split(" ");
        String[] opStrArray = postfix.replaceAll("[^[+]-[*]]", "").split("");

        String[] result = new String[numStrArray.length + opStrArray.length];
        int index = 0;
        for (int i = 0; i < numStrArray.length; i++) {
            result[index++] = numStrArray[i];

            if (i != numStrArray.length - 1) {
                result[index++] = opStrArray[i];
            }
        }
        return result;
    }

    /**
     * 연산자 우선순위 체크 로직 
     * @param op1
     * @param op2
     * @param priorities
     * @return
     */
    public static boolean compareToOperation(String op1, String op2, int[] priorities) {
        String[] op = {"+", "-", "*"};

        if (op1.equals(op[priorities[0]])) {
            if (op2.equals(op[priorities[0]])) {
                return true;
            }
        }

        if (op1.equals(op[priorities[1]])) {
            if (op2.equals(op[priorities[0]]) || op2.equals(op[priorities[1]])) {
                return true;
            }
        }

        if (op1.equals(op[priorities[2]])) {
            if (op2.equals(op[priorities[0]]) || op2.equals(op[priorities[1]]) || op2.equals(op[priorities[2]])) {
                return true;
            }
        }
        return false;
    }

 

중위표기법을 후위표기법으로 변환하였으면 후위표기법을 계산해야 한다. 

우선순위 경우의 수들에 대응한 후위표기법들의 결과값을 비교하여 가장 큰 값이 이 문제의 답이다. 

/**
     * 후위 표기법 계산 메서드 
     * @param infix
     * @return
     */
    public static long getInfixResult(String[] infix) {
        long answer = 0;
        String[] op = {"+", "-", "*"};
        Stack<String> stack = new Stack<>();

        for (int i = 0; i < infix.length; i++) {
            // 후위표기법의 현재 원소가 '연산자'인 경우 
            if (Arrays.asList(op).contains(infix[i])) {
                String operation = infix[i];

                // 스택에서 피연산자들 2개를 pop
                long second = Long.parseLong(stack.pop());
                long first = Long.parseLong(stack.pop());

                // 현재 원소의 종류에 따라 피연산자들을 계산한 결과값을 스택에 push 
                switch (operation) {
                    case "+":
                        stack.push(String.valueOf(first + second));
                        break;
                    case "-":
                        stack.push(String.valueOf(first - second));
                        break;
                    case "*":
                        stack.push(String.valueOf(first * second));
                        break;
                    case "/":
                        stack.push(String.valueOf(first / second));
                        break;
                }
            // 현재 원소가 피연산자이면 스택에 push     
            } else {
                stack.push(infix[i]);
            }
        }
        
        answer = Math.abs(Long.parseLong(stack.pop()));
        return answer;
    }

 

[JAVA code]

 

package com.algorithm.level2;

import java.util.Arrays;
import java.util.Stack;

public class Test22 {
    public static long answer = 0;
    public static String postfix = "";

    public static void main(String[] args) {
        String expression = "50*6-3*2";
        System.out.println("answer : " + solution(expression));
    }

    public static long solution(String expression) {
        answer = 0;
        postfix = expression;

        int[] items = {0, 1, 2};
        int[] buckets = new int[3];

        // 우선순위 경우의 수를 모두 구함 - 순열
        permutation(items, buckets, buckets.length);

        return answer;
    }

    /**
     * 순열 - 연산자 우선순위 경우의 수를 모두 구함
     * @param items
     * @param buckets
     * @param k
     */
    public static void permutation(int[] items, int[] buckets, int k) {
        if (k == 0) {

            // 연산자 우선순위와 중위표기법을 이용하여 후위표기법 생성
            String[] infix = postfixToInfix(postfix, buckets);

            // 후위표기법 계산 결과
            long result = getInfixResult(infix);

            // 가장 큰 값을 answer에 대입
            answer = Math.max(answer, result);
            return;
        }

        int lastIndex = buckets.length - k - 1;
        for (int i = 0; i < items.length; i++) {
            boolean flag = true;

            for (int j = 0; j <= lastIndex; j++) {
                if (buckets[j] == items[i]) {
                    flag = false;
                }
            }

            if (flag) {
                buckets[lastIndex + 1] = items[i];
                permutation(items, buckets, k - 1);
            }
        }
    }

    /**
     * 중위 표기법 -> 후위 표기법으로 변환
     * @param postfix
     * @param priorities
     * @return
     */
    public static String[] postfixToInfix(String postfix, int[] priorities) {
        // String을 배열로 변환
        String[] postfixArray = strToArray(postfix);
        String[] infixArray = new String[postfixArray.length];
        String[] op = {"+", "-", "*"};
        Stack<String> stack = new Stack<>();
        int index = 0;

        for (int i = 0; i < postfixArray.length; i++) {
            // 배열의 원소가 연산자이면
            if (Arrays.asList(op).contains(postfixArray[i])) {
                // 스택이 비어있으면
                if (stack.isEmpty()) {
                    // 연산자를 push
                    stack.push(postfixArray[i]);
                } else {
                    // 스택이 비어있지 않다면
                    // 스택에 먼저 들어있는 연산자들이 현재 연산자보다 우선순위가 높다면 pop
                    while (!stack.isEmpty() && compareToOperation(postfixArray[i], stack.peek(), priorities)) {
                        // 후위표기법 계산식에 스택에서 pop한 연산자 출력
                        infixArray[index++] = stack.pop();
                    }
                    // 현재 연산자를 스택에 push
                    stack.push(postfixArray[i]);
                }
            // 피연산자이면 후위표기법 계산식에 바로 출력
            } else {
                infixArray[index++] = postfixArray[i];
            }
        }

        // 스택에 남아있던 연산자들 모두 후위표기법 계산식에 pop하여 출력
        while (!stack.isEmpty()) {
            infixArray[index++] = stack.pop();
        }

        return infixArray;
    }

    public static String[] strToArray(String postfix) {
        String[] numStrArray = postfix.replaceAll("[^0-9]", " ").split(" ");
        String[] opStrArray = postfix.replaceAll("[^[+]-[*]]", "").split("");

        String[] result = new String[numStrArray.length + opStrArray.length];
        int index = 0;
        for (int i = 0; i < numStrArray.length; i++) {
            result[index++] = numStrArray[i];

            if (i != numStrArray.length - 1) {
                result[index++] = opStrArray[i];
            }
        }
        return result;
    }

    /**
     * 연산자 우선순위 체크 로직
     * @param op1
     * @param op2
     * @param priorities
     * @return
     */
    public static boolean compareToOperation(String op1, String op2, int[] priorities) {
        String[] op = {"+", "-", "*"};

        if (op1.equals(op[priorities[0]])) {
            if (op2.equals(op[priorities[0]])) {
                return true;
            }
        }

        if (op1.equals(op[priorities[1]])) {
            if (op2.equals(op[priorities[0]]) || op2.equals(op[priorities[1]])) {
                return true;
            }
        }

        if (op1.equals(op[priorities[2]])) {
            if (op2.equals(op[priorities[0]]) || op2.equals(op[priorities[1]]) || op2.equals(op[priorities[2]])) {
                return true;
            }
        }
        return false;
    }

    /**
     * 후위 표기법 계산 메서드
     * @param infix
     * @return
     */
    public static long getInfixResult(String[] infix) {
        long answer = 0;
        String[] op = {"+", "-", "*"};
        Stack<String> stack = new Stack<>();

        for (int i = 0; i < infix.length; i++) {
            // 후위표기법의 현재 원소가 '연산자'인 경우
            if (Arrays.asList(op).contains(infix[i])) {
                String operation = infix[i];

                // 스택에서 피연산자들 2개를 pop
                long second = Long.parseLong(stack.pop());
                long first = Long.parseLong(stack.pop());

                // 현재 원소의 종류에 따라 피연산자들을 계산한 결과값을 스택에 push
                switch (operation) {
                    case "+":
                        stack.push(String.valueOf(first + second));
                        break;
                    case "-":
                        stack.push(String.valueOf(first - second));
                        break;
                    case "*":
                        stack.push(String.valueOf(first * second));
                        break;
                    case "/":
                        stack.push(String.valueOf(first / second));
                        break;
                }
            // 현재 원소가 피연산자이면 스택에 push
            } else {
                stack.push(infix[i]);
            }
        }

        answer = Math.abs(Long.parseLong(stack.pop()));
        return answer;
    }
}