[c++] 백준 #1339 단어 수학

취미로 백준 다시 시작했다!

 

매우 깔끔한 논리로 풀 수 있는 문제였고, 오랜만에 푸는 문제였는데도 쉽게 감을 잡고 풀 수 있을 만큼 구현도 깔끔해서 오랜만의 포스팅으로 들고 왔다.

 

www.acmicpc.net/problem/1339

 

< 풀이 >

각각의 알파벳 암호가 어떤 수를 가지고 있는 지 답에서 제시하지 않아도 되므로, 알파벳 정보를 일일이 따지지 않고도 그리디하게 풀기로 했다.

 

처음 봤을 때는 자리수가 높은 순서대로 알파벳을 맵핑시킨 후 더해주면 된다는 생각이 들지만, 그보다 낮은 자리수의 알파벳이 무엇인지에 따라 답이 바뀔 수 있기 때문에 이를 고려해주는 것이 필요하다.

 

예를 들면,

2

BC

ACC

이렇게 두 수가 있을 때, 두번째 자리수에서 B와 C가 있는데 C의 갯수가 B보다 많기 때문에 A를 9, C를 8, B를 7에 맵핑해야 한다. 

 

다양한 구현 방법이 있겠지만, 가장 쉽고 빠르게 구현하는 것을 목표로(?) 다음과 같이 구현해보았다.

 

먼저, 숫자의 각각의 자리수에 대한 정보를 가진 배열을 하나 만든다. ( 1, 10, 100, 1000, …)

그 다음 모든 알파벳에 대해 해당 알파벳이 나온 자리수를 다 더해주는 길이 26의 행렬을 만들어준다.

숫자의 자리수를 하나씩 읽으며 해당 알파벳이 나온 자리수를 알파벳의 배열에 더해주고, 소팅한 후 전체 자리수 합이 큰 순서대로 9, 8, 7, 6, 5, 4, 3, 2, 1, 0을 곱해주면 된다.

(알파벳이 나온 자리수가 큰 순서대로 큰 수를 부여하면 되는 이유는, 알파벳이 나온 자리수가 크다는 것이 높은 자리수에 많은 알파벳이 등장했다는 것을 뜻하기 때문이다.)

 

복잡도 계산할 필요도 없이 숫자는 최대 10개, 알파벳은 최대 26개, 숫자 자리수는 최대 8개이므로 시간도 깔끔하게 0ms가 나오는 것을 확인할 수 있다.

 

< 소스코드 >

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

int sums[26]; // for all alphabets
int tens[10]; // 1, 10, 100, 1000, ...

int main(){
    int N;
    cin >> N;
    tens[0] = 1;
    for (int i=1;i<10;i++){
        tens[i] = tens[i-1] * 10;
    }
    for (int i=0;i<N;i++){
        string input; cin >> input;
        int sz = input.length();
        for (int i=0; i < sz; i++){
            int jari = sz - i - 1;
            sums[input[i] - 'A'] += tens[jari];
        }
    }
    int ans = 0;
    sort(sums, sums+26);
    for(int i=0; i<10;i++){
        ans += (9-i) * sums[25-i];
    }
    cout << ans << '\n';
    return 0;
}