BOJ#1339 단어 수학

BOJ#1339 단어 수학

* 문제

https://www.acmicpc.net/problem/1339

* 풀이

이 문제는 두가지 풀이법으로 풀어보겠습니다.

예)

MCR
ACDEB

1) 수학으로 풀기

위의 두 숫자를 풀어보면

MCR = M * 100 + C * 10 + R * 1

ACDEB = A * 10000 + C * 1000 + D * 100 + E * 10 + B * 1

두 숫자를 더해보면

MCR + ACDEB = 10000A + 1001C + 100M + 100D + 10E + R + B 가 됩니다.

하나의 문자는 하나의 숫자(0~9)로 대응되고

합의 최대값을 구하고 싶으므로

즉, 10000A + 1001C + 100M + 100D + 10E + R + B의 최대값을 구하면 되는 것입니다.

A -> C -> M -> D -> E -> R -> B의 순서대로 높은 값을 주면 됩니다.

2) 백트래킹으로 풀기

Backtracking으로 풀겠다는 말은, 쉽게 말해 모든 경우의 수를 시도해보겠다는 말입니다.

일단 N개의 입력받은 문자열에서 알파벳을 중복없이 뽑아냅니다.

위의 예에서는 A, B, C, D, E, M, R이 될 것이고,

9부터 3까지의 숫자를 하나씩 대입하게 될 것입니다.

즉 9~3의 숫자 배열을 permutation(순열)을 돌려 모든 경우의 수를 생성하고

이것을 본래의 식에 대입하여 (MCR + ACDEB)

max값을 찾으면 되겠습니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231339_WordMath/src

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * BOJ#1339 단어 수학
 * https://www.acmicpc.net/problem/1339
 */

// 풀이 #1. 수학으로 풀기
public class Main {

    public static void main(String[] args) throws IOException {

        int N; // 단어의 개수
        char[] alphabet; // 입력받은 단어의 총 알파벳 배열
        Integer[] weight; // 알파벳들의 가중치(합)

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        alphabet = new char[10];
        weight = new Integer[10];

        Arrays.fill(alphabet, '0');
        Arrays.fill(weight, 0);

        // 단어를 하나씩 입력 받는다
        for (int i = 0; i < N; i++) {

            String numStr = br.readLine();

            int w = 1;
            for (int j = numStr.length() - 1; j >= 0; j--) {

                char numChar = numStr.charAt(j);

                for (int k = 0; k < 10; k++) {

                    if (alphabet[k] == numChar) {

                        weight[k] += w;
                        break;
                    } else if (alphabet[k] == '0') {

                        alphabet[k] = numChar;
                        weight[k] = w;
                        break;
                    }
                }

                w *= 10;
            }
        }

        Arrays.sort(weight);

        int sum = 0;
        for (int i = 9; i >= 0; i--) {

            sum += i * weight[i];
        }

        System.out.println(sum);
    }
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;

/**
 * BOJ#1339 단어 수학
 * https://www.acmicpc.net/problem/1339
 */

// 풀이 #2. Bactraking
public class Main2 {

    static String[] numStr = new String[10];
    static int maxValue = 0;
    static int N; // 단어의 개수

    public static void main(String[] args) throws IOException {

        HashMap<Character, Integer> map = new HashMap<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        // 단어를 하나씩 입력 받는다
        for (int i = 0; i < N; i++) {

            numStr[i] = br.readLine();

            for (int j = 0; j < numStr[i].length(); j++) {

                char numChar = numStr[i].charAt(j);

                map.put(numChar, 0);
            }
        }

        int[] num = new int[map.size()];
        for (int i = 0; i < num.length; i++) {

            num[i] = 9 - i;
        }

        permutation(num, num.length, num.length, 0, map);
        System.out.println(maxValue);
    }

    static void permutation(int[] num, int k, int n, int depth, HashMap<Character, Integer> map) {

        if (depth == k) {

            // 값 대입
            Iterator<Character> it = map.keySet().iterator();
            while (it.hasNext()) {

                map.replace(it.next(), num[--k]);
            }
            // 테스트, Max 값 추출
            checkMaxValue(map);

            //System.out.println(map);

            return;
        }

        for (int i = depth; i < n; i++) {

            swap(num, depth, i);
            permutation(num, k, n, depth + 1, map);
            swap(num, depth, i);
        }
    }

    static void swap(int[] num, int i, int j) {

        int temp = num[i];

        num[i] = num[j];
        num[j] = temp;
    }

    static void checkMaxValue(HashMap<Character, Integer> map) {

        int sum = 0;

        for (int i = 0; i < N; i++) {

            String str = numStr[i];

            int exponent = 1;

            for (int j = str.length() - 1; j >= 0; j--) {

                char alphabet = str.charAt(j);

                sum += map.get(alphabet) * exponent;

                exponent *= 10;
            }
        }

        maxValue = maxValue < sum ? sum : maxValue;
    }
}