[BOJ][골4][1339] 단어 수학

문제 링크

문제링크

첫 번째 풀이 : 그리디

알고리즘

단어숫자의 각 자리수에 따라서 각 문자의 가중치를 더해줍니다.

ABC의 경우 각각 가중치 100,10,1을 더해줍니다.

가중치의 내림차순으로 정렬해서 앞에서부터 9876543210을 대입합니다. 가중치가 같은 경우는 따로 Case Work하지 않아도 됩니다.

정답코드

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

using ll = long long;
using pii = pair<int, int>;

const int MAX = 100'010;

int n, m, k;
vector<string> v(10);
pii weight[27]; // (가중치, c-'A')
int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        int w = 1;
        for (int j = s.size() - 1; j >= 0; j--, w *=10) {
            weight[s[j] - 'A'].first += w;
        }
    }
    for (int i = 0; i < 27; i++) {
        weight[i].second = i;
    }
    sort(weight, weight + 27, greater<pii>());
    ll ans = 0;
    ll num = 9;
    for (int i = 0; i < 27; i++) {
        if (weight[i].first == 0) break;
        ans += weight[i].first * num;
        num--;
    }
    cout << ans << "\n";
    return 0;
}

Success Notice: 수고하셨습니다.