[BOJ/C++] 1339: 단어 수학

🏅 Gold 4

✏️ 1차 솔루션

1. 각 단어를 탐색하면서 알파벳과 해당 알파벳이 위치한 자리를 vector 로 저장
   ➡️ 각 단어마다 해당 알파벳이 위치한 자리가 다를 수 있기 때문에 이미 해당 알파벳이 vector 에 존재하는지 확인 후, 존재하면 현재 단어에서의 자리수와 이미 저장된 자리수를 비교해서 큰 값을 넣음
2. 알파벳을 저장한 vector 를 자리수를 기준으로 내림차순 정렬
3. 알파벳 벡터 정렬 순서대로 9부터 부여
4. 저장해뒀던 단어를 돌면서 알파벳을 앞에서 부여한 숫자로 1:1 변환해서 더해주기

🚨 1차 trouble

vector 에 저장했다가 map 에 저장했다가 하면서 자료형을 너무 많이 사용하고 탐색도 빈번하게 사용하게 되어서 비효율적
애초에 방법이 잘못 된 것 같음

✏️ 최종 솔루션

⭐️ 그리디 알고리즘
자릿수가 클수록 높은 수를 배정해야 최종적으로 큰 값을 산출할 수 있기 때문에 알파벳의 자릿수를 저장한 이후 최종적으로 높은 값을 가진 알파벳 순으로 값을 곱해주는 방식으로 풀이
ex) GCF 에서 G는 100의 자리, C는 10의 자리, F는 1의 자리이고 ACDEB 에서 A 는 10000의 자리, C는 1000의 자리, D는 100의 자리, E는 10의 자리, B는 1의 자리이므로
➡️ A = 10000, C = 1000+100, D = 100, G = 100, E = 10, F= 1, B = 1

이렇게 저장한 이후, 값이 가장 큰 A 부터 9를 곱해주고 C는 8, D는 7을 곱해주는 방식으로 하면 최종적인 최대값을 구할 수 있음
어차피 같은 자리수에 대해서는 서로 바뀌어도 동일하기 때문에 같은 값에 대한 예외처리를 따로 해줄 필요는 없음

📌 self feedback

풀이가 너무 복잡해지고 배열들을 너무 더럽게 사용해야 한다면 다른 방법 고안해볼 필요가 있음

✏️ 최종 code

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    int alpha[26]={0,};
    while(n--) {
        string s;
        cin >> s;
        
        int k=s.size()-1;
        for(int i=0;i<s.size();i++) {
            int c=s[i]-'A';
            alpha[c]+=pow(10,k);
            k--;
        }
     }
    
    sort(alpha, alpha+26, greater<int>());
    
    int k=9;
    int ans=0;
    for (int i=0; i<26; i++) {
        if (alpha[i]!=0) {
            ans+=alpha[i]*k;
            k--;
        }
    }
    
    cout << ans << endl;
}