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

해당 문제 링크

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

문제 풀이

하나의 문자열로 제공해준 수식을 숫자 부분과 연산자를 분리해서 가장 큰 결과값을 나오게하면 되는 문제이다. 필요한 기능들을 정리해본다면 이렇게 나온다.

1. 수식에서 숫자들만 분리
2. 수식에서 연산자만 분리
3. 연산자의 우선순위 별로 계산
4. 절대값이 제일 큰 값 반환

수식에서 숫자들만 분리

public List<Long> findNumbers(String expression){
	List<Long> numbers = new ArrayList<>();
        
	String temp = "";
	for(int i=0; i<expression.length(); i++){
		char findChar = expression.charAt(i);
		if(findChar == '+' || findChar == '-' || findChar == '*'){
			Long number = Long.parseLong(temp);
			numbers.add(number);
			temp = "";
			continue;
		}
		temp += findChar;
	}
    
    //마지막 남은 숫자
	Long number = Long.parseLong(temp);
	numbers.add(number);
	return numbers;
}

다른 사람의 풀이를 보면 정규식으로 문자열에서 바로 split() 해서 분리하는 소스도 보았다.

수식에서 연산자만 분리

	public List<String> findOperators(String expression){
        List<String> operators = new ArrayList<>();
        
        for(int i=0; i<expression.length(); i++){
            char findChar = expression.charAt(i);
            if (findChar == '+'){
                operators.add("+");
            }else if (findChar == '-'){
                operators.add("-");
            }else if (findChar == '*'){
                operators.add("*");
            }
        }
        return operators;
    }

해당 기능도 문자열에서 숫자를 replaceAll() 해서 지운뒤에 split()한 소스도 보았는데 깔끔하니 보기 좋았다.

연산자의 우선순위 별로 계산

연산자 우선순위는 dfs를 통해서 구하려고 하다가 최대 6가지 종류밖에 나오지않아서 그냥 수동으로 제작했다.

	String[][] calculateOrders = {
            {"+", "-", "*"}, 
            {"+", "*", "-"},
            {"-", "+", "*"},
            {"-", "*", "+"},
            {"*", "-", "+"},
            {"*", "+", "-"}
    };
    
    for(int i=0; i<calculateOrders.length; i++){
		long result = 0;
		result = calculate(calculateOrders[i], numbers, operators);
		answer = Math.max(answer, Math.abs(result));
	}

1+2-3*4를 예로 들면 numbers = {1,2,3,4}, operators = {+, -, *}가 들어있고
연산우선순위는 "+ > - > *" 일 때 작업순서를 정리하면 이렇게 된다.

1. operators 에서 + 연산자를 먼저 찾는다.
2. 찾은 인덱스와 그 다음 인덱스를 numbers에서 값을 꺼내온다.(1, 2)
3. 연산자에 맞는 연산을 한다. (1+2)
4. 연산이 되었으니 operators에서 찾은 인덱스를 지운다.
5. 마찬가지로 연산이 되었으니 된 값을 해당 인덱스에 저장하고 2값에 해당하는 인덱스를 제거한다.
6. 모든 연산이 끝날때까지 반복한다.

	public Long calculate(String[] calculateOrder, List<Long> numbers, List<String> operators){
    	//복사
        List<Long> cpNumbers = new ArrayList<>(numbers);
        List<String> cpOperators = new ArrayList<>(operators);
        
        for(String operator : calculateOrder){
            while(cpOperators.contains(operator)){
            	// 1번
                int findOperatorIndex = cpOperators.indexOf(operator);
               
                // 2번
                long a = cpNumbers.get(findOperatorIndex);
                long b = cpNumbers.remove(findOperatorIndex + 1);
                
                // 3번, 5번
                if(operator.equals("+")){
                    cpNumbers.set(findOperatorIndex, a + b);
                }else if(operator.equals("-")){
                    cpNumbers.set(findOperatorIndex, a - b);
                }else{
                    cpNumbers.set(findOperatorIndex, a * b);
                }
                
                // 4번
                cpOperators.remove(findOperatorIndex);
            }
        }
        
        return cpNumbers.get(0);
    }

소스코드

import java.util.*;
class Solution {
    
    public long solution(String expression) {
        long answer = 0;

        List<Long> numbers = findNumbers(expression);
        List<String> operators = findOperators(expression);
        
        String[][] calculateOrders = {
            {"+", "-", "*"}, 
            {"+", "*", "-"},
            {"-", "+", "*"},
            {"-", "*", "+"},
            {"*", "-", "+"},
            {"*", "+", "-"}
        };
        
        for(int i=0; i < calculateOrders.length; i++){
            long result = 0;
            result = calculate(calculateOrders[i], numbers, operators);
            answer = Math.max(answer, Math.abs(result));
        }
        
        return answer;
    }
    
    public Long calculate(String[] calculateOrder, List<Long> numbers, List<String> operators){
        List<Long> cpNumbers = new ArrayList<>(numbers);
        List<String> cpOperators = new ArrayList<>(operators);
        
        for(String operator : calculateOrder){
            while(cpOperators.contains(operator)){
                int findOperatorIndex = cpOperators.indexOf(operator);
                cpOperators.remove(findOperatorIndex);
                
                long a = cpNumbers.get(findOperatorIndex);
                long b = cpNumbers.remove(findOperatorIndex + 1);
                
                if(operator.equals("+")){
                    cpNumbers.set(findOperatorIndex, a + b);
                }else if(operator.equals("-")){
                    cpNumbers.set(findOperatorIndex, a - b);
                }else{
                    cpNumbers.set(findOperatorIndex, a * b);
                }
            }
        }
        
        return cpNumbers.get(0);
    }
    
    public List<Long> findNumbers(String expression){
        List<Long> numbers = new ArrayList<>();
        
        String temp = "";
        for(int i=0; i<expression.length(); i++){
            char findChar = expression.charAt(i);
            if(findChar == '+' || findChar == '-' || findChar == '*'){
                Long number = Long.parseLong(temp);
                numbers.add(number);
                temp = "";
                continue;
            }

            temp += findChar;
        }
        
        Long number = Long.parseLong(temp);
        numbers.add(number);
        return numbers;
    }
    
    public List<String> findOperators(String expression){
        List<String> operators = new ArrayList<>();
        
        for(int i=0; i<expression.length(); i++){
            char findChar = expression.charAt(i);
            if (findChar == '+'){
                operators.add("+");
            }else if (findChar == '-'){
                operators.add("-");
            }else if (findChar == '*'){
                operators.add("*");
            }
        }
        return operators;
    }
}

---

다른사람 풀이

	String[] numbers = expression.split("[*,\\-,+]");
	char[] operators = expression.replaceAll("[0-9]", "")
    	.trim()
        .toCharArray();

이렇게 숫자부분과 연산자 부분을 분리하는 방법을 봤는데 간단하니 보기도 좋았다. 이후 연산자의 우선순위를 DFS로 찾는 사람도 있었다.