[백준] 1339 단어 수학

문제

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

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

 

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

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

 

접근 방법

제한 시간 내에 풀지 못한 문제이다. 

 

그리디 문제이기 때문에 처음 시도는 문자열의 길이가 가장 긴 것 부터 철자 하나씩 숫자로 치환하는 과정의 알고리즘을 구상하였다.

 

하지만 이 알고리즘은 철자 하나씩 치환할 때마다 모든 문자열의 철자를 검사하여 숫자로 치환해야 하기 때문에, 알고리즘을 구체적으로 구상하기 어려웠고 결국 해결하지 못하였다.

 

다른 분들이 구상한 알고리즘은 다음과 같다.

 

먼저 모든 문자열을 자릿수와 함께 표시한다.

 

예를 들어, ABCD인 경우 1000A + 100B + 10C + 1D가 된다. 이를 BECG와 더하게 된다면 

 

1000A +  1100B + 100E+ 20C + 1D + 1G가 된다.

 

알파벳을 크기에 따라 내림차순으로 나타내면 [1100B, 1000A, 100E, 20C, 1D, 1G]가 되고 순서에 따라 9 - 4까지의 수를 곱해서 모두 더하면 결과를 구할 수 있다.

 

소스 코드

파이썬

import sys

def main():
    readline = sys.stdin.readline

    N = int(readline().strip())

    alphabets = [readline().strip() for _ in range(N)]
    alphabets.sort(key=lambda x : -len(x))

    values = {}

    for alphabet in alphabets:
        pos = int(10 ** (len(alphabet)-1))

        for i in range(len(alphabet)):
            char = alphabet[i]
            if values.get(char) == None:
                values[char] = pos
            else:
                values[char] += pos
            pos = int(pos / 10)

    item_list = []
    for item in values.items():
        item_list.append(list(item))

    item_list.sort(key=lambda x : -x[1])
    
    num = 9
    result = 0
    for item in item_list:
        item[1] *= num
        result += item[1]
        num -= 1
    print(int(result))
    
if __name__ == '__main__':
    main()

자바

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			
			int N = Integer.valueOf(br.readLine());
			
			String[] words = new String[N];
			
			for(int i=0;i<N;i++) {
				words[i] = br.readLine();
			}
			
			HashMap<Character, Integer> map = new HashMap<>();
			
			for(String word : words) {
				char[] charArray = word.toCharArray();
				int pos = (int) Math.pow(10, word.length() - 1);
				
				for(char chr : charArray) {
					if(!map.containsKey(chr)) {
						map.put(chr, pos);
					} else {
						map.put(chr, map.get(chr) + pos);
					}
					pos /= 10;
				}
			}
			
			ArrayList<Integer> values = new ArrayList<>(map.values());
			
			Collections.sort(values, Collections.reverseOrder());
			
			int num = 9;
			int result = 0;
			for(int value : values) {
				result += (value * num);
				num--;
			}
			System.out.println(result);
	}

}