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

문제 설명

 

프로그래머스

 

접근 방법

우선 주어진 식(String expression)에서 숫자들과 연산자들을 분리하여 각각의 리스트에 저장하도록 했습니다.

 

    // ...
    List<Long> numbersOrigin = Arrays.stream(expression.split("[+\\-*]"))
        .map(Long::parseLong)
        .collect(Collectors.toList()); // 연산식 내 숫자 저장
            
    List<String> operators = getOperators(expression); // 연산식 내 연산자 저장
    
    // ...
        
    private List<String> getOperators(String expression) {
        List<String> operators = new ArrayList<>();
        char[] chars = expression.toCharArray();
        for (char c : chars) {
            if (c == '+' || c == '-' || c == '*') {
                operators.add(String.valueOf(c));
            }
        }

        return operators;
    }

 

이후에는 +, -, * 연산자들에 대한 각각의 우선순위를 백트래킹을 통해 탐색하면서 앞서 저장한 숫자 및 연산자 리스트를 활용하여 연산 결과를 구하도록 했습니다.

 

    Stack<String> stack = new Stack<>();
    String[] priority = {"*", "+", "-"};

    private void operate(int depth, boolean[] visited) {
        if (depth == 3) {
            result = Math.max(result, Math.abs(getOperationResult())); // 연산 결과 계산 메서드 호출
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (!visited[i]) {
                visited[i] = true;
                stack.add(priority[i]);
                operate(depth + 1, visited);
                visited[i] = false;
                stack.pop();
            }
        }
    }

 

연산 결과를 계산할 때에는 연산자 우선순위 순으로 앞서 저장한 연산자 리스트에서 연산자를 찾는데, 해당 연산자가 존재하는 위치(index) 및 해당 위치에 + 1 지점(index + 1)에 있는 피연산자(숫자)들에 대해(숫자를 저장한 리스트 참조) 해당 연산 결과를 수행해줍니다. 연산을 마친 후에는 기존 index 및 index + 1 지점에 있는 숫자를 삭제하고 새롭게 생성된 숫자를 index 지점에 추가해줍니다.

 

이 결과를 반복함으로써 최종적으로 숫자 리스트에 남는 하나의 값이 최종 연산 결과 값이 되게 됩니다.

 

    private long getOperationResult() {
        long temp;
        for (String operator : stack) {
            int index = operators.indexOf(operator);
            while (index != -1) {
                 temp = calculate(numbers.get(index), numbers.get(index + 1), operator);
                 numbers.remove(index);
                 numbers.remove(index);
                 numbers.add(index, temp);
                 operators.remove(operator);
                 index = operators.indexOf(operator);
            }
        }

        return numbers.get(0);
    }

    private long calculate(long number1, long number2, String operator) {
        if (operator.equals("*")) {
            return number1 * number2;
        } else if (operator.equals("+")) {
            return number1 + number2;
        } else {
            return number1 - number2;
        }
    }

 

전체 소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

class Solution {

    List<Long> numbers = new ArrayList<>(), numbersOrigin;
    List<String> operators = new ArrayList<>(), operatorOrigin;
    Stack<String> stack = new Stack<>();
    String[] priority = {"*", "+", "-"};
    long result = 0;

    public long solution(String expression) {
        numbersOrigin = Arrays.stream(expression.split("[+\\-*]"))
            .map(Long::parseLong)
            .collect(Collectors.toList());
        operatorOrigin = getOperators(expression);
        copy();
        boolean[] visited = new boolean[3];
        operate(0, visited);
        return result;
    }

    private void copy() {
        numbers.addAll(numbersOrigin);
        operators.addAll(operatorOrigin);
    }

    private List<String> getOperators(String expression) {
        List<String> operators = new ArrayList<>();
        char[] chars = expression.toCharArray();
        for (char c : chars) {
            if (c == '+' || c == '-' || c == '*') {
                operators.add(String.valueOf(c));
            }
        }

        return operators;
    }

    private void operate(int depth, boolean[] visited) {
        if (depth == 3) {
            result = Math.max(result, Math.abs(getOperationResult()));
            numbers.clear();
            operators.clear();
            copy();
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (!visited[i]) {
                visited[i] = true;
                stack.add(priority[i]);
                operate(depth + 1, visited);
                visited[i] = false;
                stack.pop();
            }
        }
    }

    private long getOperationResult() {
        long temp;
        for (String operator : stack) {
            int index = operators.indexOf(operator);
            while (index != -1) {
                 temp = calculate(numbers.get(index), numbers.get(index + 1), operator);
                 numbers.remove(index);
                 numbers.remove(index);
                 numbers.add(index, temp);
                 operators.remove(operator);
                 index = operators.indexOf(operator);
            }
        }

        return numbers.get(0);
    }

    private long calculate(long number1, long number2, String operator) {
        if (operator.equals("*")) {
            return number1 * number2;
        } else if (operator.equals("+")) {
            return number1 + number2;
        } else {
            return number1 - number2;
        }
    }
}

 

참고자료

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