[백준] 단어 수학

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

1339번: 단어 수학

우선 문제부터 간단하게 요약하면, 

 

단어들이 주어지게 되는데, 이 단어들은 알파벳으로 주어지게 됩니다. 이 알파벳에 0~9 까지의 숫자들을 매핑시켜서 합이 최대가 되도록 하면 되는 문제입니다. 

 

<Solution>

우선, 당연히 높은 자리 숫자에 큰 값이 들어 가야한다는 아이디어에서 출발해야 합니다. 그래서 input을 받을 때, 단어마다 각각의 가중치를 계산합니다.

예를 들면, ABC가 input으로 들어오게 되면, A의 가중치 100, B의 가중치 10, C의 가중치 1을 추가합니다. 이렇게 가중치를 전부 계산한 후 최종적으로 모든 input을 받은 뒤, 가중치가 높은 것 부터 9~0을 감소하는 순서대로 배정하면 됩니다.

 

실제 구현은 아래와 같습니다. 

(C++의 경우 가중치 계산을 하지 않고, permutation등을 사용해서 greedy 하지 않게 문제를 풀어도 해결은 가능하나 시간이 오래 걸릴 것입니다.(당연히 python 등은 불가능하겠죠.)) 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int numWord;
int mappingTable[26];
struct alphabetWeight{
    int alphaToInt;
    int weight;
};
alphabetWeight weights[26];

bool compareFunction(alphabetWeight &w1, alphabetWeight &w2){
    return w1.weight>w2.weight;
}

int main(){
    // initialize alphabetWeight
    for(int i = 0; i<26; i++){
        weights[i].alphaToInt = i;
    }

    // get input
    cin >> numWord;
    vector<string> words(numWord);

    for(int i = 0; i<numWord; i++){
        cin >> words[i];
        int k = 1;
        for(int j = words[i].length()-1; j>=0; --j){
            weights[words[i][j]-'A'].weight += k;
            k*=10;
        }
    }

    // sort
    sort(weights, weights+26, compareFunction);

    // count how many alphabets exist
    int cntAlphabets = 0;
    for(int i = 0; i<26; i++){
        if(weights[i].weight != 0) cntAlphabets++;
    }
    // assign numbers
    for(int i = 0; i<cntAlphabets; i++){
        mappingTable[i] = 9-i;
    }
    // calcuate sum
    int totalSum = 0;
    for(int i = 0; i<cntAlphabets; i++){
        totalSum += mappingTable[i] * weights[i].weight;
    }
    
    // print ans
    cout << totalSum << endl;

    return 0;

}