오늘 풀어볼 문제는 ⭐단어 수학 이라는 문제다.

1. 문제 요약

• 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제
• 같은 알파벳은 같은 숫자로 바꿔야 한다.
• 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

1.1 입력

• 10개의 문자
• 최대 길이 10글자
• 동시 포함 알파벳 최대 10개
• 수의 최대 크기 = 8글자 (천만)

2. 접근법

다음과 같이 알고리즘을 접근했다.

[알고리즘]
1. 자릿수가 높으면 무조건 높은 숫자부터 차례대로
2. 자릿수가 같으면, 빈도수가 많은 알파벳에게 큰 숫자 부여

쉽쟈냐? 하고 덤빈 문제였다.

그 러 나 . . . . . .

단순하게 높은 자릿수에 높은 번호를 부여하던 내 방식엔 큰 반례가 있었다.

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

내 알고리즘의 경우 A는 유일한 100자릿대 수라 무조건 9가 부여된다. 그러나 이 경우에는 A=8, B=9가 부여되어야 한다.

즉 가중치를 잘못 설정한 것이다.
정말 단순하게 가중치를

weight[현재 알파벳] += Math.pow(10, 현재 자릿수);

이렇게만 해주어도 문제가 쉽게 풀린다ㅠㅠ

3. 코드

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

class Info implements Comparable<Info>{
    int cDex;
    int f;

    public Info(int cDex, int f){
        this.cDex=cDex;
        this.f =f;
    }

    public int compareTo(Info o){
        return o.f-this.f;
    }

}


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        String [] input = new String[N];
        
        for (int i = 0; i < N; i++) {
            input[i] = br.readLine();
        }

        //가중치 계산
        int [] weight = new int[27];
        boolean [] check = new boolean[27];
        Arrays.fill(weight, -1);

        for (int i = 0; i < N; i++) {
            int location = 0;
            for(int j=input[i].length()-1; j>=0; j--) {
                char c = input[i].charAt(location++);
                weight[c - 'A'] += Math.pow(10, j);
            }
        }

        Queue<Info> alphaWeight = new PriorityQueue<>();

        for(int i=0; i<27; i++) {
            alphaWeight.add(new Info(i, weight[i]));
        }

        //알파벳 넘버링
        int Num = 9;
        while (!alphaWeight.isEmpty()) {
            Info now = alphaWeight.poll();
            if(check[now.cDex]) continue;
            weight[now.cDex] = Num--;
            check[now.cDex]=true;
        }

        //계산
        int answer = 0;
        for (int i = 0; i < N; i++) {
            int location = 0;
            for(int j=input[i].length()-1; j>=0; j--) {
                char c = input[i].charAt(location++);
                answer+=weight[c-'A']*(int) Math.pow(10, j);
            }
        }

        System.out.println(answer);
    }
}