[BaekJoon] 1339 단어 수학 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/1339

2.  문제

요약

• 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있습니다.
• 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제입니다.
• 같은 알파벳은 같은 숫자로 바뀌어야 하고 두 개 이상의 알파벳이 같은 숫자로 바뀌면 안 됩니다.
• N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10보다 작거나 같은 단어의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에는 알파벳은 최대 10개이고, 수의 최대 길이는 8인 단어가 주어집니다.
  • 단어는 알파벳 대문ㅁ자로만 이루어져있고 서로 다른 문자는 서로 다른 숫자를 나타냅니다.
• 출력: 첫 번째 줄에 주어진 단어의 합의 최댓값을 출력합니다.

3.  소스코드

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.Map.Entry;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static String[] words;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		words = new String[N];
		for(int i = 0; i < N; i++) words[i] = scanner.nextLine();
	}
	
	static void solution() {
		Stack<Integer> nums = new Stack<Integer>();
		for(int num = 0; num < 10; num++) nums.add(num);
		HashMap<Character, Integer> match = new HashMap<Character, Integer>();
		for(int index = 0; index < N; index++) {
			for(int str_index = 0; str_index < words[index].length(); str_index++) {
				char cur_char = words[index].charAt(str_index);
				if(!match.containsKey(cur_char)) match.put(cur_char, 0);
				match.put(cur_char, match.get(cur_char) + (int)Math.pow(10, (words[index].length() - 1) - str_index));
			}
		}
		ArrayList<Entry<Character, Integer>> entryList = new ArrayList<Entry<Character, Integer>>(match.entrySet());
		Collections.sort(entryList, new Comparator<Entry<Character, Integer>>() {
			public int compare(Entry<Character, Integer> e1, Entry<Character, Integer> e2) {
				return e2.getValue().compareTo(e1.getValue());
			}
		});
		int result = 0;
		for(Entry<Character, Integer> entry : entryList) {
			result += entry.getValue() * nums.pop();
		}
		System.out.println(result);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}

4.  접근

• 단어의 합이 최대가 되려면 주어진 단어들에서 각 알파벳이 출현하는 자릿수를 모두 확인하여 그 합이 큰 순서대로 큰 수들을 배치하면 됩니다.
• 예를 들어, 두 번째 예제처럼 GCF, ACDEB가 주어졌을 때, 각 알파벳의 자릿수를 계산하면 아래와 같습니다.
  • A = 10000
  • B = 1
  • C = 10 + 1000 = 1010
  • D = 100
  • E = 10
  • F = 1
  • G = 100
• 자릿수를 계산한 것을 보니 (A > C > D = G > E > B = F) 순서가 되므로 위에서 언급한대로 큰 순서대로 큰 수들을 배치하여 A에 9, C에 8, D에 7, G에 6, E에 5, B에 4, F에 3을 배정하면 단어의 합의 최댓값을 구할 수 있고 아래와 같이 나오게 됩니다.
  • $(10000 × 9) + (1010 × 8) + (100 × 7) + (100 × 6) + (10 × 5) + (1 × 4) + (1 × 3) = 99437$
• 위와 같은 방법을 이용하여 주어진 단어의 합의 최댓값을 구합니다.
  
  
• 주어진 단어들을 words라는 배열에 담고 Stack에 0부터 9까지 차례대로 넣습니다.
• 각 알파벳의 자릿수의 합을 저장할 HashMap을 생성합니다.
• 주어진 각 단어들의 각 알파벳들을 확인하고 해당 알파벳이 아직 HashMap에 key로 들어가있지 않다면 value를 0으로 하여 HashMap에 담고 그렇지 않다면 해당 알파벳의 자릿수를 더해가면서 이를 HashMap에 저장합니다.
• HashMap을 value 기준으로 오름차순으로 정렬합니다.
• 정렬된 HashMap의 key값들을 가져와 해당 key의 value에 Stack에서 꺼낸 값을 곱하여 합을 구합니다.
  • Stack에 수를 넣을 때 0부터 9까지 차례대로 넣었기 때문에 큰 수부터 나올 것입니다.