[ 백준, Java] 1339번 : 단어 수학

🔗 문제 링크

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

🤔 문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

😮 문제 해결 방법

자릿수가 큰 알파벳 순서로 높은 숫자를 배정해야 계산을 했을 때 가장 큰 합계가 나올 수 있다.

문제의 예제의 단어 수학 식을 자릿수로 표현해보면, GCF = 100G + 10C + 1F 로 표현할 수 있고, ACDEB = 10000A + 1000C + 100D + 10E + 1B로 표현할 수 있다.

따라서, 이렇게 자릿수로 표현한 알파벳을 각각 알파벳이 인덱스로 된 배열에 담아주고 정렬해준 후, 값이 가장 높은 알파벳부터 9부터 순서대로 배정해주면 가장 큰 합계를 얻을 수 있다.

🚩 Java 코드

package com.algorithm.Baekjoon;

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

public class Main_1339_단어_수학 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] words = new String[N];
        for(int loop =0; loop < N; loop++) {
            words[loop] = br.readLine();
        }

        int rst = getSum(words);
        System.out.println(rst);
        br.close();
    }

    private static int getSum(String[] words) {
        int[] alphabet = new int[26];

        for(String word : words) {
            int digit = word.length() - 1;
            // 알파벳 A 가 0번 인덱스, 먼저 나온 수부터 자릿수 -1씩 Loop
            for(char letter : word.toCharArray()) {
                int index = letter - 'A';
                alphabet[index] += (int) Math.pow(10,digit);
                digit--;
            }
        }

        // 정렬
        Arrays.sort(alphabet);
        int index = alphabet.length-1;
        int maxNumber = 9;
        int sum = 0;

        // 자릿수의 값이 가장 높은 순서부터 차례로 숫자 부여
        while(maxNumber >= 0 &&  alphabet[index] > 0) {
            sum += alphabet[index] * maxNumber;
            maxNumber--;
            index--;
        }
        return sum;
    }
}