[BOJ/백준][Gold3] 1132 : 합 (C++)

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

1132번: 합

 

 

[난이도] Gold3
[유형] Greedy

[풀이]
0(A)~9(J)을 저장할 수 있는 배열을 만들고 각 문자열마다 문자열을 1자리수부터 확인하면서
해당 알파벳의 해당하는 배열값에 10^자릿수 만큼을 더해준다.
그 뒤 배열값이 큰 인덱스에 해당하는 알파벳부터 9,8,7... 순서로 할당하면
가장 큰 합을 구할 수가 있다.
이 때, 맨 앞자는 0이 되면 안되므로 맨 앞에 0이 오는 알파벳에는 0을 할당하지 않도록
예외처리를 해준다.

 

#include <iostream>
#include <string>
#include <algorithm>
using ll = long long;
using namespace std;
int N,t[10];
ll v[10];
bool isF[10];
string a[50];
pair<ll,int> b[10];
int main(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> a[i];
    for(int i=0;i<N;i++){
        string s = a[i];
        ll k=1;
        for(int j=s.size()-1;j>=0;j--){
            v[s[j]-'A']+=k;
            k*=10;
        }
    }
    for(int i=0;i<N;i++) isF[a[i][0]-'A']=1;

    for(int i=0;i<10;i++) b[i]={v[i],i};
    sort(b,b+10);

    if(b[0].first!=0 && isF[b[0].second]){
        int idx=1;
        for(;;idx++) if(!isF[b[idx].second]) break;
        auto tmp = b[idx];
        for(int i=idx-1;i>=0;i--) b[i+1]=b[i];
        b[0]=tmp;
    }

    for(int i=9,j=9;i>=0;i--,j--){
        if(b[i].first==0) break;
        t[b[i].second]=j;
    }
    ll ans = 0;
    
    for(int i=0;i<N;i++){
        string s = a[i],ret;
        for(int j=0;j<s.size();j++) ret+=t[s[j]-'A']+'0';
        ans+=stoll(ret);
    }
    cout << ans;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/1132.cpp