[BOJ] 백준 1339 단어 수학

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

 Input 

2

AAA

AAA

　 

 Output 

1998　

A와 B 중 어떤 알파벳에 9를 부여할 지 고민해보아야 합니다.

 Input 

2

ABC

BCD

 

 Output 

1866

ABC → 100A + 10B + C

BCD → 100B + 10C + D

▶ ABC + BCD = 100A + 110B + 10C + D

A, B, C, D를 미지수로 생각하고 계수를 기준으로 정렬하며 다음과 같습니다.

110B + 100A +  10C + D → B = 9, A = 8, C = 7, D = 6

　

대문자 알파벳 26개가 존재하므로 다음과 같이 설정

int alphabet[26] = 알파벳 계수

ex) ABC + BCD = 100A + 110B + 10C + D

      ▶ alphabet[0] = 100, alphabet[1] = 110, alphabet[2] = 10, alphabet[3] = 1

alphabet[] 배열을 원소값 = 0을 제외하고 원소를 내림차순으로 배열하면 다음과 같다.

▶ alphabet[] = {110 , 100, 10, 1} ← 여기에 9 ~0까지 순서대로 배정하여 합을 구합니다.

---

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int N, idx, len, factor, answer;
int alphabet[26];
string str;
vector<string> vec;
 
bool cmp(int A, int B){
    if (A > B) return true;
    return false;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> str;
        vec.push_back(str);
    }
 
    for (int i = 0; i < N; i++){
        str = vec[i];
        len = str.length();
        factor = 1;
        for (int j = len - 1; j >= 0; j--){
            idx = str[j] - 'A';    
            alphabet[idx] = alphabet[idx] + factor;
            factor = factor * 10;
        }
    }
 
    // 내림차순 정렬
    sort(alphabet, alphabet + 26, cmp);
    
    int num = 9;
    for (int i = 0; i < 26; i++){
        // 계수가 큰 알파벳부터 차례대로 높은 숫자 부여
        if (alphabet[i] == 0) break;
        answer = answer + (alphabet[i] * num);
        num--;
    }
 
    cout << answer << endl;
}