[BOJ1339/Java] 단어 수학

1. 문제 요약

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

1339번: 단어 수학

골드인..이유가 있었ㄷ...

초, 중등 수학에서 많이 하던 일인데 코딩으로 막상 옮기려니까 생각이 잘 안났음.

알파벳에 숫자를 대입하는데 어떤 수를 대입해야 모든 단어의 합이 최대가 될까?

미리 얘기하자면 문자 길이나 등장 횟수만 고려해서는 답이 안나왔다..(여러번의 시도가 여기 담겨있음)

 

2. 입/출력

입출력이 정말 짧다. 시간 신경쓰지말고 구현 아이디어에 집중해야 한다..

 

3. 접근 아이디어

아까도 이야기했지만 문자 길이나 등장 횟수만 고려해서는 답이 없다.

자리수도 생각해야하고 등장 횟수도 고려해야 함. 그래서 A는 A끼리, B는 B끼리 전부 더한 값을 alpha 배열에 저장하는 것을 생각했다. 그리고 alpha 값이 큰 문자부터 큰 수를 배정해서 더하면 최댓값을 구할 수 있다.

문자열에서 index로 접근하는 방식과 자리수가 거꾸로라서 자리수에 대한 가중치를 둘 때 생각을 많이 해야했다.

 

4. 작성 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int maxLength = 0;
		String[] arr = new String[N];
		int[] alpha = new int[26];
//		int[] alcost = new int[26];
//		int alpCnt = 0;
		for (int i = 0; i < N; ++i) {
			arr[i] = br.readLine();
			if(arr[i].length() > maxLength) 
				maxLength = arr[i].length();
		}
		for(int i = 0; i<N; ++i) {
			int diff = maxLength-arr[i].length();
			for(int j = 0; j<arr[i].length(); ++j) {
//				System.out.println(arr[i].charAt(j)-'A');
				alpha[arr[i].charAt(j)-'A']+=Math.pow(10, maxLength-j-1-diff);
//				System.out.println(Arrays.toString(alpha));
			}

		}
		Arrays.sort(alpha);
		for(int i = 0; i<14; i++) {
			int t = alpha[i];
			alpha[i] = alpha[25-i];
			alpha[25-i] = t;
		}
		
		int cost = 9;
		int sum = 0;
		for(int i = 0; i<10; ++i) {
			sum += (cost--)*alpha[i];
		}
		System.out.println(sum);
	}
}