📖 [백준알고리즘 풀이] Q.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개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

🔍 접근법

단어 수학 문제입니다.

각 알파벳마다 중복되지 않게 1~9 의 숫자가 주어져야하고

단어들의 합이 최대가 되도록 해야합니다.

각 알파벳이 있는 자릿수의 값을 더 해

가장 큰값의 알파벳부터

큰 수를 대입해주면 풀 수가 있습니다.

ex) ABA
A= 10^2+10^0
B= 10^1
= A는 101 이고 B는 10 으로
A 는 9 B 는 8을 대입해주면 최대값이 나옵니다.

ex) ABACB , BDAAC
A = 10^4 + 10^2 + 10^2 + 10^1   = 10210 =>8 대입
B = 10^3 + 10^0 + 10^4          = 11001 =>9 대입
C = 10^1 + 10^0                 = 11    =>6 대입
D = 10^3                        = 1000  =>7 대입
89869 + 97866 = 187,755 가
최대값입니다.

알파벳이 위치한 각 자리의 수를 map을 이용해

넣어주었고

map의 value

각 알파벳마다의 합을 기준으로 정렬하여

큰 값부터 숫자를 대입해주었습니다.

💻 코드

package problem.greedy;

import java.io.*;
import java.util.*;

public class Main_1339 {
    static int N;
    static String words[];

    static class ValueComparator implements Comparator<Character> {

        Map<Character, Integer> base;

        public ValueComparator(Map<Character, Integer> base) {
            this.base = base;
        }

        public int compare(Character a, Character b) {
            if (base.get(a) >= base.get(b)) { //반대로 하면 오름차순 <=
                return -1;
            } else {
                return 1;
            } // returning 0 would merge keys
        }
    }


    public static void main(String[] args) throws IOException {
        Map<Character,Integer> map = new HashMap<>();
        ValueComparator valueComparator = new ValueComparator(map);
        TreeMap<Character,Integer> sortedMap = new TreeMap<>(valueComparator);
        input();
        for(int i=0; i<N; i++){
            String word = words[i];
            for(int j=0; j<word.length(); j++){
                char c = word.charAt(j);
                int num = (int) Math.pow(10 ,word.length()-j-1);
                if(map.containsKey(c) ){
                    int temp = map.get(c);
                    map.put(c,num+temp);
                }
                else{
                    map.put(c,num);
                }
            }
        }
        sortedMap.putAll(map);
        int answer = 0;
        int num = 9;
        for (Map.Entry<Character,Integer> entry : sortedMap.entrySet()) {
            System.out.println(entry.getKey()+" : "+map.get(entry.getKey()));
            int value = map.get(entry.getKey());
            answer += (value*num--);
        }
        System.out.println(answer);
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        words = new String[N];
        for(int i=0; i<N; i++){
            words[i] = br.readLine();
        }
        br.close();
    }

}

Written on November 26, 2020