백준 Gold 4 단어 수학

단어 수학 (백준 Gold 4)

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

N개의 문자열이 주어지고
각 문자를 0~9의 값으로 바꿔서
N개의 문자열이 치환된 값을 최대로 만드는 문제

ex)
2, GCF, ACDEB 가 주어진 경우
A : 9, B : 4, C : 8 , D : 6, E : 5, F : 3, G : 7로 결정한다면

783 + 98654 = 99437

풀이 방법

요점은 ‘가장 높은 자릿수’에 주어진 문자에게
높은 숫자(9 -> 8 …)를 주면 된다

또한, 양쪽 다 높은 자릿수에 있다면
더 자주 등장하는 문자가 더 높은 값을 가지게 한다

• 따라서 자릿수가 높음에 따라서
  map<char,int>에 값을 추가로 더해주는 방식을 채택하였다
  (이러면 낮은 자릿수에서 값이 나오면 값이 추가로 더해지기에
  놓치지 않음)
  (값이 끝까지 같다면, 어느쪽에 높은 쪽을 주어도 상관x)
  

• 이후 map을 vector 로 옮긴후 정렬하고
  각 value에 따라서 문자와 값을 다시 매핑해준다
  

• 마지막으로 매핑된 문자를 가지고
  원본 문자열의 값을 바꾼후 전부 더하여 출력
  

제출 코드

#include<iostream>
#include<string>
#include<unordered_map>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	unordered_map<char, int> valueMap;
	vector<string> vec;

	int n;
	cin >> n;

	while (n > 0)
	{
		string a;
		cin >> a;
		vec.push_back(a);

		int aSize = a.size();

		for (int i = 0; i < aSize; i++)
		{
			valueMap[a[i]] += pow(10, aSize - i - 1);
		}
		n--;
	}
	
	vector<pair<char, int>> valuev(valueMap.begin(), valueMap.end());
	sort(valuev.begin(), valuev.end(), [](const pair<char, int>& a, const pair<char, int>& b) 
		{
			return a.second > b.second;
		});

	int now = 9;
	unordered_map<char, int> mapping;
	for (auto& a : valuev)
	{
		mapping[a.first] = now;
		now--;
	}

	int sum = 0;

	for (auto& a : vec)
	{
		int v = 0;

		for (char c : a)
		{
			v *= 10;
			v += mapping[c];
		}

		sum += v;
	}

	cout << sum;

	return 0;
}

결과

코드를 조금 더 깔끔하게 짤수 없을까 싶은 아쉬움이 있다