백준 1339 (단어 수학)

문제

1339번: 단어 수학

n개의 영어 대문자로 주어진 문자열이 주어진다.

문자열의 알파벳에 0 ~ 9 까지의 숫자를 부여한뒤 n개의 문자열을 더했을 때 가장 큰 수가 나오게 하는 문제이다.

0~9 까지 이기 때문에 주어지는 모든 문자열의 알파벳은 최대 10가지이다.

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

---

처음에는 단순히 문자열의 길이가 가장 긴 순서대로 정렬한 후에 자릿수가 높은 알파벳에 가장 큰 수를 주는 방식으로 구현하려 했었다.

하지만 위에 예시와 같이 ACDEB 와 GCF를 보면 ACDEB가 문자열의 길이가 길기 때문에 98765 이런식으로 결정하려 했지만, 

결과는 AC까지는 자릿수가 높기 때문에 맞지만, DEB의 D와 GCF의 G는 누가 더 높은 우선순위를 가질지 애매해졌다.

결국 방법을 찾지 못하고 구글링의 정보를 찾았다.

 

어차피 정답은 모든 문자열의 "합" 이기 때문에 각 알파벳마다 자릿수를 더해주었다.

예를 들어 ACDEB는 10000(A) + 1000(C) + 100(D) + 10(E) + 1(B) 형식이다.

또 GCF = 100(G) + 10(C) + 1(F) 로 정해주었다.

그렇게 되면 결국 10000(A) * 9 + 1010(C) * 8 + 100(G 또는 D) * 7 + 100(G 또는 D) * 6 + 10(E 또는 C) * 5 + 10(E 또는 C) * 4 + 1(B 또는 F) * 3 + 1(B 또는 F) * 2 이다.

---

전체 코드이다.

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

        int n = Integer.parseInt(st.nextToken());

        Map<Character, Integer>map = new HashMap<>();
        for(int i = 0;i<n;i++) {
            String s = br.readLine();
            for(int j=0;j<s.length();j++) {
                Character c = s.charAt(j);
                if(!map.containsKey(c)) {
                    map.put(c, power(s.length()-j-1));
                }
                else{
                    int target = map.get(c);
                    map.put(c, target + power(s.length()-j-1));
                }
            }
        }

        List<Integer>list = new ArrayList<>(map.values());
        Collections.sort(list, Collections.reverseOrder()); //계산된 알파벳 값을 기준으로 내림차순 정렬
		[10000, 1010, 100, 100, 10, 10, 1, 1]
        
        int injection = 9;
        int ans = 0;
        for(Integer i : list){
            ans += injection * i;
            injection--;
        }

        System.out.println(ans);
    }
    private static int power(int z){
        int num = 1;
        for(int i = 0;i<z;i++){
            num *=10;
        }
        return num;
    }
}