백준 1339, 단어 수학

개요

문제 링크
골드 4, Greedy
알파벳마다 숫자를 할당해 변환한 수의 최대 합 구하기

---

접근

1. 그리디한 문제라고 한다면 무조건 가장 최적의 알파벳을 찾아 숫자를 할당해야 함. 그 기준을 찾는 과정이 어려운 것.
2. 기준을 어떻게 찾나? 하면 우선 가장 높은 자리수의 수에 가장 큰수를 할당하는 것을 생각할 수 있음.

ACCC -> 9888
 BDD -> 766
// A에 높은 수를 할당하는 것이 가장 최선

위의 사례에서 당연히 A에 9를 할당하는 것이 최선임을 알 수 있다. 그럼 다음 수는? B와 C의 최대자리수가 100으로 같다. 만약 A에서 Z까지 for문을 돌리면 B부터 8을 할당할테니 최선이 아니다.

3. 아 그럼 큰 자리수부터 비교해가면서 등장 횟수가 더 큰 경우가 발견되면 먼저 큰 수를 할당하면 되겠구나. 말로 하면 애매하니

ACCC
 BDD

// compare B, C
B -> [0,1,0,0]
C -> [0,1,1,1]

이렇게 각 자리수마다의 등장횟수의 배열을 만들고 정렬한 뒤 stoi를 써서 더해줬는데 WA떴음.

4. 뭐가 문제일까? 하다가 아하 배열이 아닌 그냥 수를 써버리면 되는구나.

ACCC
 BDD

A -> 1000 (9)
C -> 111 (8)
B -> 100 (7)
D -> 11 (6)

즉 문자열을 순회하면서 각 알파벳이 발견되면 10^(자리수)를 알파벳의 고유값에 더해주고, 고유값을 바탕으로 정렬해서 순서대로 9부터 0까지 할당한 뒤, 고유값 × 할당한 숫자의 총합을 구해주면 됨.

---

Pseudo code

for (i = 0~n)
    l = len(string)
    for (j = 0~l)
        v[string[j]] += 10^(l-1-j)
sort(v)
num = 9
for (x : v)
    answer += (num--)*x

---

Source code

#include <bits/stdc++.h>
using namespace std;

const int A = 26;
int v[A];

int main() {
    int n;
    cin >> n;
    string s;

    for (int i=0; i<n; i++) {
        cin >> s;
        int l = s.size();
        for (int j=0; j<l; j++) {
            int k = s[j]-'A';
            v[k] += pow(10,l-1-j);
        }
    }
    sort(v, v+A);
    int b = 9;
    int ans = 0;
    for (int i=A-1; i>=0; i--)
        if (b)
            ans += (b--)*v[i];
    cout << ans;
}