[백준/JAVA] BOJ 1339- 단어 수학

👀 문제

1339번: 단어 수학 ✨ 골드 4

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

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

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

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

예제 입력

2
GCF
ACDEB

예제 출력

99437

🔑 키포인트

그리디 알고리즘 자릿수 해시맵

✍️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BOJ1339 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		ArrayList<char[]> words = new ArrayList<char[]>();
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		ArrayList<Integer> nums = new ArrayList<Integer>(); 
		
		int n = Integer.parseInt(st.nextToken());
		
		// 입력
		for (int i = 0; i < n; i++) {
			String wd = br.readLine();
			int len = wd.length();
			char[] ch = new char[len];
			for (int j = 0; j < len; j++) {
				ch[j] = wd.charAt(j);
			}
			words.add(ch);
		}
		
		// 자릿수 계산
		for (char[] ch : words) {
			for (int i = 0; i < ch.length; i++) {
				char c = ch[i];
                // 해시맵에 키로 없다면 추가
				if (!map.containsKey(c)) {
					int number = (int) Math.pow(10, (ch.length - i - 1));
					map.put(c, number);
				} else { // 키가 있다면 기존 값에 더하여 추가
					int number = (int) Math.pow(10, (ch.length - i - 1));
					map.replace(c, map.get(c) + number);
				}
			}
		}
		
		// 맵 value 기준으로 내림차순
		for (int v : map.values()) {
			nums.add(v);
		}
        
		Collections.sort(nums, Collections.reverseOrder());
		
		int result = 0;
		int start = 9;
		
        // value가 큰 것부터 차례대로 9부터 곱해 주기
		for (int i = 0; i < nums.size(); i++) {
			result += nums.get(i) * start;
			start--;
		}
		
		System.out.println(result);
	}
}