[백준/BOJ] 백준 1339번 : 단어 수학

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

1339번: 단어 수학

 

전체 단어에 나온 알파벳을 vector<char> alpha에 저장해 놓은 뒤, sort(alpha.begin(), alpha.end()); alpha.erase(unique(alpha.begin(), alpha.end()), alpha.end());을 통해 중복된 알파벳을 지우고, 해당 알파벳이 몇 번째 인덱스에 위치하는지 저장해 놓았다(map<char, int> alpha_index). 그리고 각 알파벳에 부여할 숫자를 가장 큰 숫자(9)부터 하나씩 알파벳의 개수만큼 저장해 놓고 저장해 놓은 숫자들(vector<int> perm)의 모든 순열을 확인하여 i번째 인덱스에 위치하는 알파벳에 perm[i]숫자를 부여하는 경우를 확인하는 방법으로 문제를 해결했다.

 

코드

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

int n;
vector<char> alpha;
map<char, int> alpha_index; //해당 알파벳이 몇번째 인덱스에 있는지 확인
vector<string> word;
int result = -1;

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		for (int j = 0; j < input.size(); j++) {
			alpha.push_back(input[j]);
		}

		word.push_back(input);
	}

	//중복된 알파벳 지우기
	sort(alpha.begin(), alpha.end());
	alpha.erase(unique(alpha.begin(), alpha.end()), alpha.end());

	for (int i = 0; i < alpha.size(); i++) {
		alpha_index.insert(make_pair(alpha[i], i));
	}

	//알파벳에 부여할 숫자를 가장 큰 숫자(9)부터 하나씩 알파벳의 개수만큼 넣는다
	vector<int> perm;
	for (int i = 9; i >= (int)(10 - alpha.size()); i--) {
		perm.push_back(i);
	}

	sort(perm.begin(), perm.end());

	do {

		//i번째 알파벳에 perm[i]숫자를 부여했을 경우 확인

		int sum = 0;

		for (int i = 0; i < word.size(); i++) {

			int add = 1;
			for (int j = word[i].size() - 1; j >= 0; j--) {
				sum += (perm[alpha_index[word[i][j]]] * add);
				add *= 10;
			}

		}

		result = max(result, sum);

	} while (next_permutation(perm.begin(), perm.end()));

	cout << result;

	return 0;
}