[PROGRAMMERS] 수식 최대화 - JAVA

1. 문제

프로그래머스

3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식

전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출

단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없음. 
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출

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

---

2. 풀이

공통 변수

int[][] total_order	연산자 우선순위 경우의 수. +,-,* 순서
Map<String,Inteter> op	연산자 별 total_order의 인덱스 번호 저장
ArrayList<String> origin	입력받은 수식을 숫자, 연산자로 쪼개 저장한 중위 연산식 list
ArrayList<String> exp	입력받은 수식을 숫자, 연산자로 쪼개 저장한 후위 연산식 list

 

초기화

Map에 연산자 별 인덱스 번호를 저장하고, 입력받은 String형식 연산식을 list로 변환하는 메서드를 호출한다.

    public void init(String expression) {
        op.put("+", 0);
        op.put("-", 1);
        op.put("*", 2);

        convertToList(expression);
    }

 

String 연산식 list로 변환

1.  연산자가 아니라면 tmp라는 StringBuilder에 더한다.

2.  연산자라면 기존 tmp에 담긴 값을 모두 String으로 변환 후 origin에 추가한다. 새로운 StringBuilder 객체를 만든다.

3.  반복이 모두 끝났다면 마지막 숫자를 String으로 변환해 origin에 추가한다.

    public void convertToList(String expression){
        origin = new ArrayList<>();
        StringBuilder tmp = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) != '+' && expression.charAt(i) != '-' && expression.charAt(i) != '*') {
                tmp.append(expression.charAt(i));
            } else {
                origin.add(tmp.toString());
                origin.add(expression.charAt(i) + "");
                tmp = new StringBuilder();
            }
        }
        origin.add(tmp.toString());
    }

 

후위 연산식으로 변환

중위 연산식을 파라미터로 받은 연산자 우선순위에 따라 후위연산식으로 변환한다.

1.  중위 연산자에 있는 요소를 하나씩 탐색하면서

1-1.  만약 연산자이고 stack에 담겨있는 연산자 중 현재 연산자보다 우선순위가 높거나 같은 게 있다면 후위연산식 리스트(exp)에 추가한다. 그 후 stack에 현재 연산자를 추가한다.

1-2.  만약 숫자라면 바로 exp에 추가한다.

2.  탐색이 끝난 후 stack이 빌 때까지 exp에 연산자를 추가한다.

    public void convert(int[] order){
        exp = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        for(String item:origin){
            if(item.equals("+") || item.equals("-") || item.equals("*")){
                while(!stack.isEmpty() && order[op.get(stack.peek())] >= order[op.get(item)]){
                    exp.add(stack.pop());
                }
                stack.push(item);
            }else{
                exp.add(item);
            }
        }

        while(!stack.isEmpty()) exp.add(stack.pop());
    }

 

연산식 계산

1.  먼저 파라미터로 받은 연산순위를 이용해 중위 연산식을 후위 연산식으로 변환한다.

2.  후위 연산식의 요소를 하나씩 탐색하면서, 

2-1.  연산자라면 앞과 뒤 숫자를 꺼내서 계산하고, 그 값을 숫자 스택에 더한다.

2-2.  숫자라면 숫자 스택에 더한다.

3.  만약 숫자 스택에 마지막으로 남은 값이 0보다 작다면 문제 조건에 따라 절댓값을 반환한다. 0보다 크거나 같다면 그대로 반환한다.

    public long calc(int[] order){
        convert(order);
        Stack<Long> number = new Stack<>();

        for(String item:exp){
            if(item.equals("+") || item.equals("-") || item.equals("*")){
                long second = number.pop();
                long first = number.pop();
                number.push(calc(first, second, op.get(item)));
            }else{
                number.push(Long.parseLong(item));
            }
        }

        if(number.peek()<0) return -number.pop();
        return number.pop();
    }

 

두 숫자와 연산자 이용한 계산

+ : 0, - : 1, * : 2 에 맞춰서 a와 b를 계산한 뒤 반환한다.

    public long calc(long a, long b, int operator) {
        long result = a;
        switch (operator) {
            case 0:
                result += b;
                break;
            case 1:
                result -= b;
                break;
            case 2:
                result *= b;
                break;
        }

        return result;
    }

 

Main

1.  초기화 메서드를 호출한다.

2.  반환할 long type 변수를 만들고, 6가지의 연산 우선순위를 모두 적용해서 계산한 후 그 최댓값을 저장한다.

3.  최댓값을 반환한다.

    public long solution(String expression) {
        init(expression);

        long max = 0;

        for (int i = 0; i < 6; i++) {
            long result = calc(total_order[i]);
            if (max < result) max = result;
        }

        return max;
    }

 

전체 코드

import java.util.*;

class Solution {
    int[][] total_order = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};//+-*
    Map<String, Integer> op = new HashMap<>();
    ArrayList<String> origin, exp;
    
    public void init(String expression) {
		op.put("+", 0);
		op.put("-", 1);
		op.put("*", 2);

		convertToList(expression);
	}
       
    public long solution(String expression) {
		init(expression);

		long max = 0;

		for (int i = 0; i < 6; i++) {
			long result = calc(total_order[i]);
			if (max < result) max = result;
		}

		return max;
    }
        
    public void convertToList(String expression){
		origin = new ArrayList<>();
		StringBuilder tmp = new StringBuilder();
		for (int i = 0; i < expression.length(); i++) {
			if (expression.charAt(i) != '+' && expression.charAt(i) != '-' && expression.charAt(i) != '*') {
				tmp.append(expression.charAt(i));
			} else {
				origin.add(tmp.toString());
				origin.add(expression.charAt(i) + "");
				tmp = new StringBuilder();

			}
		}
		origin.add(tmp.toString());
	}
    
    public void convert(int[] order){
		exp = new ArrayList<>();
		Stack<String> stack = new Stack<>();
		for(String item:origin){
			if(item.equals("+") || item.equals("-") || item.equals("*")){
				while(!stack.isEmpty() && order[op.get(stack.peek())] >= order[op.get(item)]){
					exp.add(stack.pop());
				}
				stack.push(item);
			}else{
				exp.add(item);
			}
		}

		while(!stack.isEmpty()) exp.add(stack.pop());
	}
    
    public long calc(int[] order){
		convert(order);
		Stack<Long> number = new Stack<>();

		for(String item:exp){
			if(item.equals("+") || item.equals("-") || item.equals("*")){
				long second = number.pop();
				long first = number.pop();
				number.push(calc(first, second, op.get(item)));
			}else{
				number.push(Long.parseLong(item));
			}
		}

		if(number.peek()<0) return -number.pop();
		return number.pop();
	}
    
    public long calc(long a, long b, int operator) {
		long result = a;
		switch (operator) {
			case 0:
				result += b;
				break;
			case 1:
				result -= b;
				break;
			case 2:
				result *= b;
				break;
		}

		return result;
	}

}

---

3. 결과