[백준] Greedy: 단어수학

문제

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

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

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

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

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

 

문제 접근

각 알파벳이 특정 숫자와 대응된다고 할 때 두 수의 합의 최대값을 구하는 문제이다.

특징으로는 다음과 같이 숫자가 알파벳으로 대체되어 제시된다는 것이다.

 

처음에는 각 자리에 어떤 숫자가 들어갈지 정하는게 핵심이라고 생각했다.

결국 위의 수는 자리수대로 구분하면 위와 같이 정리할 수 있다.

따라서 이를 [ [A], [C], [G, D], [C, E], [F, B] ]의 배열로 정리하여 9부터 차례대로 대응시키고자 했다.

 

하지만 이는 중복되는 숫자가 있을 경우 처리가 애매할 수 있다.

 

다음과 같은 경우가 있다고 해보자.

A를 9로 할것이냐, B를 9로 할것이냐에 따라 결과가 달라진다.

이는 단순히 배열 순서대로 숫자를 부여하는 방법은 적용할 수 없다는 것을 의미하다.

 

그렇다며 좀 더 확실한 방법은 무었이 있을 까?

 

결국 구하고자 하는 것은 합의 최대 값이다. 그럼 합은 어떻게 표현할까?

 

위의 예시를 본다면 (100B+10A+A)+(100A+10A+B) = 100(A+B) + 10(A+A) + (A+B) 라고 표현할 수 있다?

 

하지만 이렇게 정리하면 배열 순서대로 한 것과 다름이 없다. A 와 B의 순서를 파악할 수 없다.?????

 

알파벳의 순서가 있어야 한다? 즉, 각 알파벳으로 묶어서 정리해야한다. 

 

 (100B+10A+A)+(100A+10A+B)  = (100+10+10+1)A+ (100+1)B = 121A + 101B 로 정리할 수 있다.

 

쉽게말해 A가 가장 많이 나오고 B가 다음이라고 할 수 있다.

 

즉, 위와 같이 알파벳 별 자릿수를 쭉 더했을 때 내림차순으로 정리하여 9부터 차례대로 숫자를 부여하면, 

최대값을 보장할 수 있다.

 

한마디로 알파벳 별 자리수의 합의 크기를 기준으로 정렬하여 무조건 큰 수부터 대응시켜주면 된다. --> Greedy

 

풀이 코드

package baekjun;

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        //목적: 합의 최댓값을 구하자.

        //문자열 받기.
        String[] alphabets = new String[N];

        for (int i=0; i<N; i++){
            alphabets[i] = br.readLine();
        }

        //HashMap에 알파벳 별 자리수 저장.
        HashMap<String, Integer> alphabetNum = new HashMap<>();


        //앞에 자리수 붙이기.
        for (String number : alphabets) {
            int tens = (int) Math.pow(10, number.length()-1);

            String[] splitAlphabet = number.split("");

            for (int i=0; i<splitAlphabet.length; i++){
                //StringBuilder가 더 빠름
                StringBuilder sb = new StringBuilder();
                sb.append(tens);
                sb.append(splitAlphabet[i]);
                splitAlphabet[i] = sb.toString();

                //알파벳과 숫자 부분 발라내기
                String s = splitAlphabet[i];
                String k =s.substring(s.length()-1, s.length());
                int v = Integer.parseInt(s.substring(0, s.length()-1));

                //Map에 알파벳, 자리수 저장, 이미 있는 경우 더해주기.
                alphabetNum.put(k, alphabetNum.getOrDefault(k, 0)+v);

                //자리수 감소
                tens /= 10;
            }
        }

        //max는 9부터 시작
        int num = 9;
        int answer = 0;
        ArrayList<Integer> numArr = new ArrayList<>(alphabetNum.values());

        //내림차순 정리
        numArr.sort(Collections.reverseOrder());
        for (Integer integer : numArr) {
            answer += num*integer;
            num--;
        }

        System.out.println(answer);
    }
}