[백준1339] 단어 수학 (C++)

📌 문제

BOJ 바로가기

알파벳을 숫자로 치환해서 두 단어의 값을 더했을 때의 최댓값을 구하는 문제이다.

🔎 풀이

그리디 알고리즘을 이용해 풀 수 있다.

예제 입력

2
GCF
ACDEB

각 단어에서 알파벳의 가중치(자릿수)는 다음과 같다.
GCF -> G = 100, C = 10, F = 1
ACDEB -> A = 10000, C = 1000, D = 100, E = 10, B = 1

각 알파벳의 가중치를 합친 후 가중치가 큰 순서대로 정렬하면 다음과 같다.
A = 10000, C = 1010, D = 100, G = 100, E = 10, B = 1, F = 1

가중치가 큰 알파벳부터 큰 숫자를 부여해주면 쉽게 답을 구할 수 있다.
10000*9 + 1010*8 + 100*7 + 100*6 + 10*5 + 1*4 + 1*3 = 99437

🚩 소스코드

#include <iostream>
#include <queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, alpha[26] = { 0, };
    string word[10];
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> word[i];
    // 알파벳 배열에 자릿수 가중치 더해주기 (ex. alpha[0] = 10010 : a가 10000의 자리와 10의 자리에 위치한 경우)
    for(int i = 0; i < n; i++){
        int digit = 1;
        for(int j = word[i].length() - 1; j >= 0; j--){
            int k = word[i][j] - 'A';
            alpha[k] += digit;
            digit *= 10;
        }
    }
    // 가중치가 높은 순서대로 정렬
    priority_queue<pair<int, int>> q;
    for(int i = 0; i < 26; i++){
        if (alpha[i])
            q.push({alpha[i], i});
    }
    // 가중치가 높은 순서대로 9에서부터 1 줄여가며 곱해서 ans에 더해줌
    int ans = 0;
    int temp = 9;
    while(!q.empty()){
        ans += q.top().first * temp;
        q.pop();
        temp--;
    }
    cout << ans;
}