[코드트리] 알파벳과 사칙연산(Java)

문제 링크

[https://www.codetree.ai/trails/complete/curated-cards/test-calculations-with-alphabet/description]

내 풀이

import java.util.*;

public class Main {

    static char[] input;
    static int size;
    static int max = Integer.MIN_VALUE;

    static Map<Character, Integer> map;
    static Set<Character> alph;
    static List<Character> list;

        // 알파벳에 숫자 매핑하기
    static void recur(int idx) {
        if (idx == size) {
            int res = calculate();
            max = Math.max(max, res);
            return;
        }

        for (int i = 1; i <= 4; i++) {
            map.put(list.get(idx), i);
            recur(idx+1);
            map.remove(list.get(idx));
        }
    }

        // 매핑된 결과를 가지고 수식 계산하기
    static int calculate() {
        int cur = map.get(input[0]);
        for (int i = 1; i < input.length - 1; i += 2) {
            switch (input[i]) {
                case '-':
                    cur -= map.get(input[i+1]);
                    break;
                case '+':
                    cur += map.get(input[i+1]);
                    break;
                case '*':
                    cur *= map.get(input[i+1]);
                    break;
            }
        }

        return cur;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        input = sc.next().toCharArray();

        // 알파벳 종류 뽑아내기
        alph = new HashSet<>();
        for (int i = 0; i < input.length; i += 2) {
            alph.add(input[i]);
        }
        // 재귀 돌리기 위해 list로 변환
        list = new ArrayList<>(alph);
        // 알파벳 - 숫자 매핑
        map = new HashMap<>();
        size = list.size();

        recur(0);
        System.out.println(max);
    }
}

과정

아이디어

• 초기에는 입력받은 수식을 재귀 돌면서 알파벳을 숫자로 바꿨다

• 근데 수식 초반에서 b를 2로 바꾸면 수식 뒷부분에서 b가 나오면 자동으로 2로 설정해야 된다

• 그럼 뒷 부분에서 backtracking할 때, 골치 아파진다

• 다시 문제를 읽고 생각해보니 꼭 수식을 돌면서 알파벳을 숫자로 바꿀 필요가 없었다

• 알파벳은 a ~ f로 고정이고 바꿀 숫자의 범위도 1 ~ 4로 고정이었다

• 그래서 우선 입력을 받고 Set에 알파벳을 넣으면 해당 수식에 들어있는 알파벳 종류를 알 수 있다

• 이걸 다시 List로 만들고 알파벳에 숫자 할당하는 걸 재귀함수로 돌린다.

• 예를 들어 수식에 알파벳이 b, d, f 가 나왔다면

• b = 1, d = 1, f = 1 부터 b = 4, d = 4, f = 4까지 모든 경우의 수를 만든다

• 그리고 매번 경우의 수 완성될 때마다, 알파벳을 숫자로 바꿔서 계산해주고 최댓값을 구하면 된다.