백준 1339번 단어 수학 (C++)

문제 링크 : www.acmicpc.net/problem/1339

1339번: 단어 수학

문제 풀이는 다음과 같다. 

1. 벡터 3개를 준비한다.

1개는 문자열을 담을 string 벡터 원본.

1개는 문자열에 사용된 알파벳들을 중복을 제거해서 저장할 char 벡터.

다른 1개는 위의 알파벳 벡터에 따른 숫자들을 저장할 벡터이다.

2. 문자열을 저장하고 문자열에 사용된 알파벳들을 저장한다.

3. 이때 알파벳들은 unique함수를 사용해 중복을 제거하여 문자열을 저장해준다.

sort(letters.begin(), letters.end()); 
letters.erase(unique(letters.begin(),letters.end()),letters.end()); // unique를 쓰기위해 sort는 필수

 4. 알파벳의 갯수에 따라 사용하게될 숫자들을 저장한다.

for(int i=9; i>9-m; i--){
	nums.push_back(i);
}

5. Next Permutation을 사용하여 최대값을 찾아준다. 이때 Next Permutation을 사용하기 위해 숫자 배열을 sort해주는 것을 잊지말자.

char alphas[256];

int comp(vector<string> &origin, vector<char> &letters, vector<int> &nums){
	int res = 0; 
	for(int i=0; i<nums.size(); i++){
		alphas[letters[i]] = nums[i]; // 이 부분을 잘 이해해야한다
	}
	for(string s : origin){
		int now = 0;
		for(char c : s){
			now*=10;
			now+=alphas[c];
		}
		res += now;
	}
	return res;
}

참고로 알파벳 문자에 숫자를 저장해주기위해 alphs[256]라는 문자형 배열을 따로 만들었다. 

256으로 사이즈를 배정한 이유는 아스키코드의 갯수 때문이다.

 

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

int n=0;
unsigned long long maxi = 0;
char alphas[256];

int comp(vector<string> &origin, vector<char> &letters, vector<int> &nums){
	int res = 0; 
	for(int i=0; i<nums.size(); i++){
		alphas[letters[i]] = nums[i];
	}
	for(string s : origin){
		int now = 0;
		for(char c : s){
			now*=10;
			now+=alphas[c];
		}
		res += now;
	}
	return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	vector<string> v(n); // 원본
	vector<char> letters; //원본 알파벳 단어만 저장
	vector<int> nums; // 사용할 숫자를 저장
	for(int i=0; i<n; i++){
		string s;
		cin >> s;
		v.push_back(s);
		for(char a : s) letters.push_back(a);
	}
	sort(letters.begin(), letters.end()); 
	letters.erase(unique(letters.begin(),letters.end()),letters.end()); // unique를 쓰기위해 sort는 필수
	int m = letters.size(); 
	for(int i=9; i>9-m; i--){
		nums.push_back(i);
	}
	sort(nums.begin(), nums.end());
	do{
		int temp = comp(v, letters, nums);
		if(maxi<temp) maxi = temp;
	}while(next_permutation(nums.begin(), nums.end()));
	cout << maxi << "\n";
	return 0;
}