문제 이해하기

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

• 같은 순위의 연산자는 없어야 합니다 ( 2개 이상의 연산자가 동일한 우선순위를 가질 수는 없습니다 )
• 수식에 포함된 연산자가 두개라면 → 연산자 우선순위 조합은 2!개가 가능, 연산자가 3개라면 3! 개의 조합이 가능하다.
• 심지어 계산결과가 음수인 경우 → 절대값으로 변환한 값이 최대이면, 얘가 우승자임!

문제 풀기

파악해야할 것

• 포함되어있는 연산자가 뭐뭐 있는지

  • 주어진 연산자들로 가능한 조합 만들기
    • backtrace
  • 주어진 조합으로, 연산식의 글자들을 큐 에 넣으면서, 현재 찾는 연산자가 아니면 모두 스택에 넣는다.현재 찾는 연산자라면 연산결과를 넣는다.
    • expression 의 길이가 100 이하고, 연산자는 최대 3가지 이기 때문에
    1. 연산자 조합은 최대 6가지가 나온다.
    2. 6가지 조합동안 거의 모든 수 ( 100개)를 확인해도 시간복잡도는 매우 낮다.

• 만들어진 조합의 연산자 우선순위 순서 ex) - + 를 바탕으로, expression 에, 가장 높은 우선순위의 연산자를 사용하여 먼저 연산하고 -> 그 다음 연산자로 연산 -> 그 다음 연산자로 연산 을 수행합니다
  - 이 때, 3 - 4 - 5 8 + 100 과 같은 경우, 3-4 를 연산한 결과에 -5 를 해야합니다.

  • 저는 두 개의 양방향 큐를 사용했습니다. original, copy
    • original 에 있는 것을 순차적으로 탐색합니다 -> 목표 연산자가 아니면 copy 에 넣습니다 -> 목표 연산자를 만나면 copy 의 top 에 있는 것을 꺼내오고, original 에서 연산자 다음 원소를 꺼내와서 연산을 수행합니다 -> 연산 결과를 copy에 넣습니다.

• 각 조합에 대해 위 과정을 거친다면 max 값을 구할 수 있겠죠?

구현해보기

조합 구현하기를 까먹었군용?🥲 백트레이스를 사용해서 조합을 구해보았습니당

마음에 들지 않는 코드입니당.. operator 를 비교하려고 모두 string 으로 쪼개서 하고 있는데 Long, Character 로 쪼개서 하는게 더 좋을가 같네요.

import java.util.*; 
import java.util.stream.Collectors;

class Solution {
    private boolean[] visit;
    private String[] priority;
    private static Set<String> criteria = Set.of("*", "+", "-"); // 문제에서 이 연산자들만 나온다했음
    private long max = 0;

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

        List<String> existingOperators = findOperators(expression);
        int opCount = existingOperators.size();
        priority = new String[opCount];
        visit = new boolean[opCount];
        recursive(0, opCount, existingOperators, expression);

        answer = max;
        return answer;
    }

    private List<String> findOperators(String expression) {
        return expression.chars().mapToObj(c -> (char)c)
            .map(c -> Character.toString(c))
            .filter(c -> criteria.contains(c))
            .distinct()
            .collect(Collectors.toList());
    }

    private void recursive(int numb, int size, List<String> operators, String expression) {
        if (numb >= size) {
            // 생성된 조합으로 연산하자
            max = Math.max(max, evaluate(expression));
            return;
        }
        for (int i = 0; i < size; i++) {
            if (visit[i]) {
                continue;
            }
            visit[i] = true;
            priority[numb] = operators.get(i);
            recursive(numb + 1, size, operators, expression);
            visit[i] = false;
        }
    }

    private Long evaluate(String expression) {
        LinkedList<String> origin = parse(expression);
        LinkedList<String> copy = new LinkedList<>();
        int opCount = priority.length; // 연산자 개수
        if (opCount == 0) {
            return Long.parseLong(expression);
        }

        for (int i = 0; i < opCount; i++) {
            // 연산자 개수만큼 반복한다
            // 먼저 해당 연산자로 연산한 결과를 넎는다.
            int size = origin.size();
            for (int idx = 0; idx < size; idx++) {
                // 현재 우선순위인 연산자를 만나면 계산한다
                if (origin.get(idx).equals(priority[i])) {
                    long evaluated = calculate(origin.get(idx), copy.pollLast(), origin.get(idx + 1));
                    idx++;
                    copy.addLast(Long.toString(evaluated));
                }
                else {
                    copy.addLast(origin.get(idx));
                }
            }

            origin = new LinkedList(copy);
            copy.clear();
        }

        return Math.abs(
            Long.parseLong(
                origin.getLast()
            ));

    }

    private Long calculate(String operator, String op1, String op2) {
        long result = 0;
        switch (operator) {
            case "+":
                result = Long.parseLong(op1) + Long.parseLong(op2);
                break;
            case "-":
                result = Long.parseLong(op1) - Long.parseLong(op2);
                break;
            case "*":
                result = Long.parseLong(op1) * Long.parseLong(op2);
                break;
        }

        return result;
    }

    private LinkedList<String> parse(String expression) {
        int start = 0, end = 0;
        LinkedList<String> components = new LinkedList<>();
        for (end = 0; end < expression.length(); end++) {
            // idx 가 연산자 인경우
            if (criteria.contains(Character.toString(expression.charAt(end)))) {
                components.addLast(expression.substring(start, end));
                components.addLast(expression.substring(end, end + 1));
                start = end + 1;
            }
        }
        components.addLast(expression.substring(start, end));
        return components;
    }
}

어굴어굴..

바꿀 때가 된 것 같다
파이썬 코드는 엄청 짧더라 🥲 나는 왜 Java 로 이 문제를 풀고 있는가...
1차 클론코딩 기간 끝나면 파이썬으로 코테 푸는 연습해야겠다