백준_1339_단어수학

📍문제: https://www.acmicpc.net/problem/1339

1339번: 단어 수학

 

📍알고리즘: 브루트포스 - 순열 (Greedy 또는 브루트포스-재귀로도 풀 수 있음)

 

📍아이디어: ASCII 코드를 이용해서 char형 배열을 다른 배열의 index로 사용해서 알파벳을 숫자로 치환.

 

🔭 벡터 중복 제거 방법:

반드시 sort 한 후에 unique 함수를 이용해서 제거.

// alphabets 벡터 중복 제거
sort(alphabets.begin(), alphabets.end());
alphabets.erase(unique(alphabets.begin(), alphabets.end()), alphabets.end());

 

📍코드:

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

using namespace std;

int N; // 단어 개수
char alpha[128]; // 해당 인덱스의 알파벳이 어떤 숫자로 바뀌는지 저장 (인덱스는 ASCII 코드)

int calc(vector<string>& wordArr, vector<char>& alphabets, vector<int>& numbers) {
	int s = alphabets.size();
	int sum = 0;
	for (int i = 0; i < s; i++) {
		alpha[alphabets[i]] = numbers[i]; // 알파벳을 숫자로 치환
	}

	for (string word : wordArr) {
		int now = 0;
		for (char x : word) {
			now = now * 10 + alpha[x];
		}
		sum += now;
	}
	return sum;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	vector<string> wordArr(N);
	vector<char> alphabets; // 단어에 어떤 알파벳들이 있는지
	for (int i = 0; i < N; i++) {
		cin >> wordArr[i];
		for (char letter : wordArr[i]) {
			alphabets.push_back(letter);
		}
	}

	// alphabets 벡터 중복 제거
	sort(alphabets.begin(), alphabets.end());
	alphabets.erase(unique(alphabets.begin(), alphabets.end()), alphabets.end());
	int s = alphabets.size();
	vector<int> numbers;
	for (int i = 9; i > 9 - s; i--) { // 최대값을 구하는 문제니까 9부터 알파벳 개수만큼 숫자 고르기
		numbers.push_back(i);
	}

	// 순열 최대값 구하기
	int ans = 0;
	do {
		int tmp = calc(wordArr, alphabets, numbers);
		if (ans < tmp) {
			ans = tmp;
		}
	} while (prev_permutation(numbers.begin(), numbers.end()));

	cout << ans << '\n';
	return 0;
}