[JAVA] 백준 1339번: 단어수학

 

 

문제풀이 

알파벳으로 이루어진 여러 문자열이 주어지고,

이 문자열끼리 덧셈을 해야하는데 가장 큰 값을 도출하도록 알파벳에 숫자를 할당해야하는 문제이다.

 

예를 들어, ABAB + CCDD를 한다고 가정하면

C = 9, A=8, B=7, D=6 이 들어가야 할 것이다.

 

값의 범위는 0~9 이고, 큰 값부터 한개씩 가장 큰 자리수에 존재하는 알파벳에 한개 씩 할당해 주면 된다.

 

가장 큰 자리수에 존재하는 알파벳은 어떻게 알아낼 것인가?

 

ABAB = (1000 * A) + (100 + B) + (10 * A )+ (1 * B)

CCDD = (1000 * C) + (100 + C) + (10 * D)+ (1 * D)

 

A = 1010

B = 101

C = 1100

D = 11

 

위와 같이 연산하면 C > A > B > D 순으로 값이 커야 두 수의 합이 최대가 될 수 있다.

각각의 알파벳에 큰 값부터 할당해 주면 결과적으로 알파벳은 아래와 같은 값을 지니게 된다.

A = 8

B = 7

C = 9

D = 6

 

위와 같은 로직을 코드로 변경해보자.

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
import java.util.Map.Entry;

public class baekjoon1339 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String ary[] = new String[n];
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String temp = sc.next();
            ary[i] = temp;
            for (int j = 0; j < temp.length(); j++) {                
                char alpha = temp.charAt(j); 
                int num = (int) Math.pow(10, temp.length()-j-1);
                if (map.get(alpha) == null) {
                    map.put(alpha, num);
                } else {
                    map.put(alpha, map.get(alpha)+num);
                }
            }
        }                
        List<Entry<Character,Integer>> list_entries = new ArrayList<>(map.entrySet());        
        
        Collections.sort(list_entries, new Comparator<Entry<Character, Integer>>() {
			// compare로 값을 비교
			public int compare(Entry<Character,Integer> obj1, Entry<Character,Integer> obj2) {
				// 오름 차순 정렬
				return obj2.getValue() - obj1.getValue();
			}
		});
        
        int count = 9;
        for (Entry<Character,Integer> entry : list_entries) {            
            Character alpha = entry.getKey();
            map.put(alpha, count--);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            String temp = ary[i];
            String resTemp = "";
            for (int j = 0; j < temp.length(); j++) {
                char alpha = ary[i].charAt(j);                       
                resTemp += map.get(alpha);
            }
            res += Integer.parseInt(resTemp);            
        }
        System.out.println(res);
    }
}