처음에 들어온 문자열을 문자로 쪼개서 문자들을 sort해서 next_permutation을 돌렸다. 돌리면서 한 문자에 어떤 숫자가 들어가는 지 결정하고, 또 문자열을 쪼개서 다 합한 것을 계산했다. 뭐라 설명해야할 지 모르겠고, 그냥 미친 짓이였다.
올바른 접근
받은 스트링이 ABCDE가 있다면, 이를 10000 * A + 1000 * B + 100 * C + 10 * D + 1 * E처럼 해석 하는 것이다.
나는 map<char, int> m을 선언해서 char에는 문자를, int에는 숫자를 넣어줬다.
map에 다 넣은 뒤, map의 int 기준으로 내림차순 정렬을 하려고 했다. 그래서 새 구조체를 선언했고, map을 vector로 변환하는 과정을 거쳤다.
// 구조체
struct Le{
char letter;
int value;
Le(char a, int b){
letter = a;
value = b;
}
bool operator < (const Le & b) const {
return value > b.value;
}
};
// 벡터로 변환하는 과정
for(auto & i : m){
if(i.second != 0){
exist.push_back(Le(i.first, i.second));
}
}
내림차순 정렬을 하고, 정렬한 원소 순서대로 9, 8, 7, ...을 넣어서 계산해주면 된다.
int cnt = 9;
sort(exist.begin(), exist.end());
for(auto i : exist){
answer += (cnt * i.value);
cnt--;
}
코드
#include <bits/stdc++.h>
using namespace std;
struct Le{
char letter;
int value;
Le(char a, int b){
letter = a;
value = b;
}
bool operator < (const Le & b) const {
return value > b.value;
}
};
int n, answer;
string temp;
map<char, int> m;
vector<Le> exist;
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> temp;
for(int i = 0; i < temp.length(); i++){
m[temp[i]] += pow(10, temp.length() - i - 1);
}
}
for(auto & i : m){
if(i.second != 0){
exist.push_back(Le(i.first, i.second));
}
}
int cnt = 9;
sort(exist.begin(), exist.end());
for(auto i : exist){
answer += (cnt * i.value);
cnt--;
}
cout << answer;
}