[algorithm] 백준 - 단어수학

이 문제를 greedy로 풀었다.

 

알파벳 별로 자릿수를 더한 수를 구한 후 배열 내에 담는다.

ABCA

A) 1001
B) 100
C) 10

 

 

for(int i = 0; i < wordVector.size(); i++){
        int powNum = 1;
        for(int j = wordVector[i].size() - 1; j >= 0; j--){
            word[wordVector[i][j] - 'A'] += powNum;
            powNum *= 10;
        }
    }

 

그리고 알파벳 배열을 내림차순으로 정렬 후 9부터 0까지 자릿수를 더한 수와 곱하면 알파벳 수의 합을 최대로 만들 수 있다.

 

9009 + 800 + 70 = 9879

 

 

sort(word, word + 26, compare);
    int number = 9, answer = 0;
    for(int i = 0; i < 26; i++){
        if(word[i] == 0) continue;
        answer += word[i] * number;
        number--;
    }

 

코드는 이렇게 구현했다.

 

//단어 수학
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool compare(int a, int b){
    return a > b;
}
int main(void){
    int count;
    string str;
    vector<string> wordVector;
    int word[26] = {0,};
    cin >> count;
    for(int i = 0; i < count; i++){
        cin >> str;
        wordVector.push_back(str);
    }
    for(int i = 0; i < wordVector.size(); i++){
        int powNum = 1;
        for(int j = wordVector[i].size() - 1; j >= 0; j--){
            word[wordVector[i][j] - 'A'] += powNum;
            powNum *= 10;
        }
    }
    sort(word, word + 26, compare);
    int number = 9, answer = 0;
    for(int i = 0; i < 26; i++){
        if(word[i] == 0) continue;
        answer += word[i] * number;
        number--;
    }
    cout << answer;

}