[BOJ] 1339 - 단어 수학

1. 문제 해석

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

1339번: 단어 수학

• 알파벳 대문자로 이루어진 N개의 단어가 주어진다.
• 이때, 각 알파벳 대문자를 0~9 중 하나로 바꿔서 N개의 수를 합한다.
• 같은 알파벳은 같은 숫자로 바꿔야 하고, , 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
• 모든 단어에 포함된 알파벳은 최대 10개를 넘지 않는다.
• 알파벳과 숫자를 매칭 하여 주어진 단의 합의 최댓값을 구해야 한다.

2. 접근방법

N개의 단어에 포함된 알파벳을 최대 10개이다. 이중 어떤 알파벳에 높은 수를 매칭해야 단어의 합의 최대를 구할 수 있을까? 우리가 높은 수를 매칭 해야 할 알파벳의 조건은 다음과 같다. 'N개의 단어에 얼마나 자주 등장하는 가?'와 '해당 알파벳의 자릿수가 높은가?'이다. 예를 들어, N = 2이고 단어는 각각 BCF, ACDE이라 하면 두 개의 단어 중 가장 높은 자리는 A(1000자리)이다. B(100자리)와 C(100자리)는 최대 자리 수가 갖지만 C는 두 단어 모두에 포함되어 있다. 따라서 A = 9, B = 7, C = 9, D = 6, E = 5, F = 4 또는 A = 9, B = 7, C = 9, D = 6, E = 4, F = 5로 결정하는 것이 단어의 합의 최대 값이다.

 

3. 주의할 점

• N개의 단어에 A가 아무리 많이 포함되어 있더라도 B가 더 높은 자릿수라면 우선 권을 갖는다.

 

4. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>

using namespace std;

int N, ans, aVal[26], score[26];
vector<string> words;
vector<char> a_vec[10];
vector<int> n_vec;

void setValue() {
	vector<pair<int, int>> vec;
	for (int i = 0; i <= 'Z' - 'A'; i++) {
		if (score[i] > 0) vec.push_back({ score[i], i });
	}
	sort(vec.begin(), vec.end());
	int num = 9;
	for (int i = vec.size() - 1; i >= 0; i--) {
		aVal[vec[i].second] = num;
		num--;
	}
}

int getValue(string s) {
	int ret = 0;
	for (char c : s) {
		int idx = c - 'A';
		ret = ret * 10 + aVal[idx];
	}
	return ret;
}

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

	cin >> N;
	int nSize = 0;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		words.push_back(str);
		int len = str.size();
		nSize = max(nSize, len);
		for (int j = len; j > 0; j--) {
			int ten = 1;
			for (int k = 1; k < j; k++) ten *= 10;
			int idx = str[len - j] - 'A';
			score[idx] += ten;
		}
	}

	setValue();
	for(string s : words) ans += getValue(s);
	
	cout << ans << '\n';

	return 0;
}