[BOJ] 백준 1339번 단어 수학 (Java)

#1339 단어 수학

난이도 : 골드 4

유형 : 그리디

1339번: 단어 수학

▸ 문제

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

단어 수학 문제는 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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

▸ 출력

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

 

문제 풀이  

그리디하게 각 알파벳에 수를 부여하여 가장 큰 숫자를 출력하면 된다. 주어진 문자들 중 가장 높은 자릿수를 가지는 알파벳 순대로 높은 수를 부여해주면 된다. 

• 가장 높은 자릿수를 가지는 알파벳 순대로 높은 수를 부여하는 것이다. 만약 높은 수를 부여하지 않은 경우 큰 값을 가질 수 없으므로 해당 선택에는 최적해가 반드시 존재하게 된다.
• 최적 부분 구조 또한 남아있는 수 중 큰 값을 부여하면 되므로 그리디 탐색 속성에 성립된다.

 

따라서, 각 알파벳 자릿수 크기대로 값을 정렬한 후 각 순위에 맞는 수를 부여해주면 최적해를 구할 수 있다.

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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());
		
		Map<Integer, Integer> map = new HashMap<>();
		for(int i=0; i<n; i++) {
			char[] ch = br.readLine().toCharArray();
			for(int j=ch.length-1; j>=0; j--) {
				int pow = (int)Math.pow(10, ch.length-1-j);
				map.put(ch[j]-'A', map.getOrDefault(ch[j]-'A', 0)+pow);
				
			}
		}
		
		List<Integer> keyList = new ArrayList<>(map.keySet());
		Collections.sort(keyList, (o1,o2) -> (map.get(o1) - map.get(o2)));
		
		int total=0;
		int num = 10-map.size();  
		for(int key : keyList) {
			total += map.get(key)*num;
			num++;
		}
		System.out.println(total);
	}
}