[백준 1339] 단어 수학 (C++)

https://www.acmicpc.net/problem/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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

---

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

 

문제 풀이

---

그리디 문제.

 

합이 최댓값이 되려면 큰 자릿수에 큰 수부터 할당해주어야 한다. 따라서 모든 알파벳이 한번씩만 사용되면 큰 자리수부터 9~0를 할당해주면 된다. 그러나 한 알파벳이 여러 자릿수에 존재하고, 그것이 여러 개 존재하면 아무거나 할당해주면 안된다. 큰 자릿수에 큰 수를 할당해주어야 합이 최댓값이 될 수 있으므로, 각 자릿수를 바탕으로 알파벳간의 우선순위를 만들어 우선순위가 큰 알파벳에게 큰 숫자를 할당해준다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;

int pow(int A, int B)
{
	int num = A;
	for (int i = 1; i < B; i++)
	{
		num *= A;
	}
	return num;
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	int maxLength = 0;
	long long answer = 0;
	priority_queue<pair<int, int>> pq;
	cin >> N;
	string* str = new string[N];
	int* calculatedNumbers = new int[N];
	int* prioritys = new int[26];
	int* allocatedNumbers = new int[26];
	for (int i = 0; i < 26; i++)
	{
		allocatedNumbers[i] = -1;
		prioritys[i] = 0;
	}
	int current = 9;
	for (int i = 0; i < N; i++)
	{
		cin >> str[i];
		calculatedNumbers[i] = 0;
		maxLength = max(maxLength, (int) str[i].length());
	}
	for (int i = 0; i < N; i++)
	{
		str[i] = str[i].insert(0, maxLength - str[i].length(), '0');
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < maxLength; j++)
		{
			if (str[i].at(j) == '0')
			{
				continue;
			}
			int index = str[i].at(j) - 'A';
			prioritys[index] += pow(10, maxLength - j);
		}
	}

	for (int i = 0; i < 26; i++)
	{
		if (prioritys[i] != 0)
		{
			pq.push(pair(prioritys[i], i));
		}
	}

	while (!pq.empty())
	{
		pair<int, int> top = pq.top();
		allocatedNumbers[top.second] = current;
		current--;
		pq.pop();
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < maxLength; j++)
		{
			if (str[i].at(j) == '0')
			{
				continue;
			}
			int index = str[i].at(j) - 'A';
			calculatedNumbers[i] = calculatedNumbers[i]*10 + allocatedNumbers[index];
		}
	}

	for (int i = 0; i < N; i++)
	{
		answer += calculatedNumbers[i];
	}
	cout << answer << "\n";
	return 0;
}