[알고리즘-자바] 프로그래머스 2020 카카오 인턴십 > 수식 최대화

문제

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

프로그래머스

언어

자바 Java

로직

토큰 분리

입력받은 expression을 연산자를 기준으로 구분하여 토큰을 저장합니다. 여기서 split()을 사용하게 되면 연산자를 저장할 수가 없기 때문에 StringTokenizer를 사용해야 합니다. StringTokenizer에 대해서는 여기를 참고해주세요.

// 연산자를 구분자로 사용하여 토큰 분리
StringTokenizer st = new StringTokenizer(expression, "+-*", true);
List<String> list = new ArrayList<>();
while (st.hasMoreTokens()) {
    list.add(st.nextToken());
}

// 예시
입력 : "1+2-3*4+5"
토큰 : 1, +, 2, -, 3, *, 4, +, 5

연산자 조합

문제에서 주어진 연산자는 "+", "-", "*" 세 개입니다. 우선순위에 따라 연산자를 사용하여 계산해야 합니다. 따라서 다음과 같이 6가지의 연산자 조합을 만들어줍니다. 

// 연산자 3개로 만들 수 있는 연산자 조합, 우선순위 적용됨
String[][] operators = {
        "+-*".split(""),
        "+*-".split(""),
        "-+*".split(""),
        "-*+".split(""),
        "*+-".split(""),
        "*-+".split("")
};

연산자에 따른 계산

switch-case문을 사용하여 연산자에 따라 계산을 다르게 처리합니다.

// 계산
private long calculator(String operator, long num1, long num2) {
    switch (operator) {
        case "+":
            return num1 + num2;
        case "-":
            return num1 - num2;
        case "*":
            return num1 * num2;
        default:
            return 0;
    }
}

계산하기

list에는 위에서 표현식을 토큰으로 분리한 토큰들이 저장되어 있습니다. 연산자마다 리스트를 전체 순환해야 합니다. 

왜냐하면 1 + 2 - 4 + 5인 경우 1 + 2와 4 +5 두 번을 계산해야 하기 때문입니다.

private long calculator(String[] operator, List<String> list) {
    // operator에는 연산자 우선순위가 적용된 연산자 조합이 저장되어 있다.
    for (String op : operator) {
        for (int i = 0; i < list.size(); i++) {
            if (op.equals(list.get(i))) {
                long num1 = Long.parseLong(list.get(i - 1));
                long num2 = Long.parseLong(list.get(i + 1));
                long result = calculator(op, num1, num2);

                // 위에서 계산한 값과 연산자 제거
                list.remove(i - 1);
                list.remove(i - 1);
                list.remove(i - 1);
                // 위에서 계산한 값 추가
                list.add(i - 1, String.valueOf(result));
                i -= 1;
            }
        }
    }
    return Long.parseLong(list.get(0));
}

위에서 list.remove(i - 1)을 세 번을 왜 수행해야 할까요? 다음 예를 들어보겠습니다.

표현식 1 + 2 - 4 + 5이 존재합니다. 연산자 "+"의 우선순위가 가장 높을 때 "+"에 대해서 먼저 계산을 해야 합니다.

그렇다면 (1 + 2) - 4 + 5 괄호 친 부분부터 먼저 계산을 해야겠죠. 계산 후 1 + 2 수식은 제거되야 할 뿐만 아니라 1 + 2 값인 3을 수식에 추가해야 합니다. 즉 3 - 4 + 5가 되어야 합니다. 이를 구현하기 위해 list.remove(i - 1)을 사용해야 합니다.

1 + 2 - 4 + 5 // index : 1 -> '+'를 가리키고 있음
list.remove(i-1)
+ 2 - 4 + 5 // index : 1 -> '2'를 가리키고 있음
list.remove(i-1)
2 - 4 + 5 // index : 1 -> '-'를 가리키고 있음
list.remove(i-1)
- 4 + 5 //index : 1 -> '4'를 가리키고 있음

이제 1 + 2 값인 3을 저장해야 합니다. - 앞에 3을 위치시켜야 하므로 다음과 같이 코드를 작성합니다. 

- 4 + 5 // index : 1 -> '4' 가리키고 있음
list.add(i - 1, 1 + 2 계산 값)
3 - 4 + 5

마지막으로 i - 1을 수행해야 하는 이유는 i를 앞으로 당겨줘야 '-'부터 연산을 다시 시작할 수 있습니다.

현재 index가 1이고 index - 1을 하면 index는 0을 가리키게 됩니다. 이때 반복문이 1회 종료되므로 i++이 수행됨에 따라 다시 index는 1을 가리키게 됩니다. 따라서 '-'부터 반복문을 실행하면서 표현식을 다시 탐색하게 됩니다.

---

코드

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Solution {
    public long solution(String expression) {

        // 연산자를 구분자로 사용하여 토큰 분리
        StringTokenizer st = new StringTokenizer(expression, "+-*", true);
        List<String> list = new ArrayList<>();
        while (st.hasMoreTokens()) {
            list.add(st.nextToken());
        }

        // 연산자 3개로 만들 수 있는 연산자 조합, 우선순위 적용됨
        String[][] operators = {
                "+-*".split(""),
                "+*-".split(""),
                "-+*".split(""),
                "-*+".split(""),
                "*+-".split(""),
                "*-+".split("")
        };

        long max = 0;
        for (String[] operator : operators) {
            // 음수는 양수로 변경한다
            long result = Math.abs(calculator(operator, new ArrayList<>(list)));
            max = result > max ? result : max;
        }

        return max;
    }
    
    private long calculator(String[] operator, List<String> list) {
        // operator에는 연산자 우선순위가 적용된 연산자 조합이 저장되어 있다.
        for (String op : operator) {
            for (int i = 0; i < list.size(); i++) {
                if (op.equals(list.get(i))) {
                    long num1 = Long.parseLong(list.get(i - 1));
                    long num2 = Long.parseLong(list.get(i + 1));
                    long result = calculator(op, num1, num2);

                    // 위에서 계산한 값과 연산자 제거
                    list.remove(i - 1);
                    list.remove(i - 1);
                    list.remove(i - 1);
                    // 위에서 계산한 값 추가
                    list.add(i - 1, String.valueOf(result));
                    i -= 1;
                }
            }
        }
        return Long.parseLong(list.get(0));
    }

    // 계산
    private long calculator(String operator, long num1, long num2) {
        switch (operator) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "*":
                return num1 * num2;
            default:
                return 0;
        }
    }
}