[Boj] C++ #1339 단어 수학

📍 문제 링크

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

 

📍 알고리즘 분류

그리디

 

📍 문제 풀이

직관적으로 높은 자리에 큰 수가 와야된다는 것을 파악할 수 있다. 그런데 단어가 하나가 아니기 때문에, 어떤 단어에서는 높은 자리수의 알파벳이 다른 단어에서는 가장 낮은 자리수에 위치해있을 수도 있다. 따라서 모든 단어를 종합하여 판단해야 한다.

 

ABC와 CADB가 주어졌다고 해보자.

단어 수의 합은 (100*A + 10*B + C) + (1000*C + 100*A + 10*D + B) = (1000*C + 200A + 11B + C)가 될 것이다.

이게 최대가 되기 위해서는 가장 큰 수를 곱하는 알파벳부터 9, 8, 7, 6, .. 순서대로 바꿔주면 된다.

따라서 C = 9, A = 8, B = 7, C = 6으로 변환하면 된다.

 

이 로직을 적용해서 문제를 해결할 수 있다.

알파벳의 개수만큼인 26의 크기를 가지고 있는 alphabet 배열을 만든다.

해당 배열에는 단어를 입력 받을 때마다 알파벳 하나씩을 보면서 자리수 값을 저장해둔다.

예를 들어 ABC일 때, alphabet[A] = 100, alphabet[B] = 10, alphabet[C] = 1이 저장된다.

모든 단어를 거친 후에는 전체 단어에서 해당 알파벳의 자리수 합이 들어갈 것이다.

 

알파벳 배열을 정렬한다.

가장 큰 수부터 9를 곱해주고, 다음으로 큰 수에는 8을 곱해주고 ... 하면 된다.

 

알파벳 배열에서 인덱스는 알파벳을 나타내는 정보를 가지고 있는데, 여기서 알파벳을 정렬해도 된다는 것을 이해하기 어려웠다.

알파벳 정렬 시 인덱스 값은 사라지는게 맞지만, 즉 어떤 알파벳의 자리수가 가장 큰지 알 수 없게 되는 것이 맞지만

핵심은 이 문제에서 그 정보가 필요 없다는 것이다.

단어 합의 최댓값만 구하면 되므로 어떤 알파벳이 어떤 숫자로 변환되고가 중요하지 않다.

그냥 가장 큰 수부터 순서대로 9부터 그 아래까지 곱하고 더해주면 되는 것이다.

이 부분이 가장 핵심적인 부분인 것 같다.

 

 

📍 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n; cin>>n;
    vector<int> alpha(26,0);
    string tmp;
    for(int i=0;i<n;i++){
        cin>>tmp;
        int pow = 1;
        for(int j=tmp.size()-1;j>=0;j--){
            alpha[tmp[j]-'A'] += pow;
            pow *= 10;
        }
    }

    sort(alpha.begin(),alpha.end());
    int num = 9;
    int ans = 0;

    for(int i=alpha.size()-1;i>=0;i--){
        if(alpha[i]==0) break;
        ans += (alpha[i]*num);
        num--;
    }
    cout<<ans<<endl;
}

 

문제 풀이에 도움을 받은 블로그 : https://0m1n.tistory.com/66

 

 

알파벳 배열을 정렬하는 부분이 가장 신기했다. 인덱스 값을 무시해도 최댓값을 구하는 해답은 도출해낼 수 있다.