백준 1339 - 단어 수학

문제링크

• 백준 1339

문제설명

• 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다.
• 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
• 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.
• N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

문제접근

• 문제의 핵심은 알파벳에 숫자를 할당하는 순서를 결정하고 해당 순서대로 높은 숫자를 할당하는 것이다. 따라서, 알파벳들의 우선순위를 결정하는 것이 중요하다.
• 처음에는 가장 자릿값이 큰 문자부터 높은 우선순위를 부여하면 된다고 생각했다. 그러나, 간과했던 점은 전체 자릿값이 같은 문자들의 경우 전체 문자열에서 등장하는 빈도가 많은 문자부터 우선순위를 부여해야 한다는 점이었다.
• 모든 문자의 빈도를 계산하는 것은 따져야 하는 경우가 매우 많다고 생각했다. 백의자리에서 등장하는 빈도가 많은 문자.. 십의자리에서 등장하는 빈도가 많은 문자.. 등 고려해야 하는 점이 복잡하고 많아서 각 문자에 가중치를 부여하는 방법을 떠올리게 되었다.
• 각 문자를 자릿값에 따라 1000, 100, 10, 1 의 값을 누적하여 해당 문자의 가중치를 결정한다. 그리고 가중치가 큰 문자들부터 높은 숫자를 부여하여 숫자로 변화했을 때 그 합을 최대로 만들 수 있다.

구현

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

vector<string> strList;
vector<pair<int, int>> alphaWeight(26, { 0,0 });
bool used[10] = { false, };
char alphaNum[26];

void SetWeight()
{
	for(auto str:strList)
	{
		int length = str.length();
		for (int i = 0; i < length; i++)
		{
			int idx = str[i] - 'A';
			int val = pow(10, length - i - 1);
			alphaWeight[idx].first += val;
		}
	}
}

void Init()
{
	for (int i = 0; i < 26; i++)
	{
		alphaWeight[i].first = 0;
		alphaWeight[i].second = i;
		alphaNum[i] = 'N';
	}
}

char GetNumber()
{
	for (int num = 9; num >= 0; num--)
	{
		if (used[num] == false)
		{
			used[num] = true;
			return (char)num + '0';
		}
	}
	return 'X'; // 발생하면 안됨
}

void SetNumber()
{
	for (int i = 0; i < 26; i++)
	{
		if (alphaWeight[i].first == 0) break;
		int idx = alphaWeight[i].second;
		if (alphaNum[idx] == 'N') // 숫자가 결정되지 않은 경우
		{
			alphaNum[idx] = GetNumber();
		}
	}
}

int AddAllNumbers()
{
	int ret = 0;
	for (auto str : strList)
	{
		string nstr;
		for (int i = 0; i < str.length(); i++)
		{
			int idx = str[i] - 'A';
			nstr.push_back(alphaNum[idx]);
		}
		ret += stoi(nstr);
	}
	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int N, ans = 0;;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		strList.push_back(str);
	}
	Init();
	SetWeight();
	sort(alphaWeight.begin(), alphaWeight.end(), greater<pair<int, int>>()); // 내림차순 정렬
	SetNumber();
	ans = AddAllNumbers();
	cout << ans << endl;
	return 0;
}