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

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

순열로 풀게 되면 시간 초과가 날 것이고, 다른 방법이 필요하다.

ABC 이런 문자열이 있으면, C에는 1의 가중치를, B에는 10의 가중치를, A에는 100의 가중치를 준다. 

마찬가지로 또 다른 문자열 AR이 있다고 하면, A에는 10의 가중치를, R에는 1의 가중치를 준다.

그렇다면 전체 가중치는 A에 110, B에 10, C에 1 R에 1일 것이다. 이를 가중치 내림차순으로 사용된 알파벳만 골라서

110 * 9 + 10 * 8 + 1 * 7 + 1 * 6 이렇게 계산해주면 된다. 

즉 높은 가중치에서부터 9부터 1씩 감소하면서 곱해주면 된다.

#pragma warning(disable :4996)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
 
int cnt[26], n;
 
bool cmp(int a, int b) {
    return a > b;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
 
    vector<string> wrd;
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        wrd.push_back(tmp);
    }
 
    
    for (int i = 0; i < wrd.size(); i++) {
        int val = 1; //가중치
        for (int j = wrd[i].length()-1; j >= 0; j--) { //문자열 우측부터 읽음
            cnt[wrd[i][j] - 'A'] += val; 
            val *= 10; // 좌측(자리수가 커지는 방향) 갈 때마다  
        }
    }
    
    vector<int> usedAlpha; 
    for (int i = 0; i < 26; i++) 
        if (cnt[i] > 0) //사용된 문자
            usedAlpha.push_back(cnt[i]);//사용된 문자만 벡터에 담음
    
    sort(usedAlpha.begin(), usedAlpha.end(), cmp); //가중치 내림차순으로 정렬
    
    ll ans = 0; int num = 9;
    for (int i = 0; i < usedAlpha.size(); i++)
        ans += usedAlpha[i] * num--; //가중치 큰 알파벳부터 9씩 곱해서 더해주면 됨
 
    cout << ans;
 
    return 0;
}