[C++] 단어 수학 (1339번)

단어 수학

 

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

---

문제풀이

내 생각대로 풀어보려다가, 너무 너무 비효율적이라고 생각되어 결국 해답을 찾아본 문제다. 그리디 알고리즘은 쉬운 거 같으면서도 어려운 것 같다.

 

핵심 아이디어를 떠올리는 것이 중요하다.

1. 알파벳 길이만큼의 배열을 하나 만든다. 0으로 초기화한다.

2. 문자열을 입력받아 하나하나 보며 해당 자릿수만큼을 배열에 추가해 준다.

ex) ABB -> arr[A] = 100, arr[B] = 11

모든 입력에 대해 이를 반복한다.

3. 알파벳을 내림차순으로 정렬한다.

4. 맨 앞부터 *9, *8 하며 정답에 더해준다.

 

이런 생각을 도대체 어떻게 떠올린 건지 신기하다. 나의 고민 시간이 부족했나 라는 생각도 든다. 사실 저렇게 정렬을 생각하진 못했지만, 최고 자릿수가 ABC CAB와 같이 A, C 일 경우 어떻게 더 큰 값을 정할지에 대한 고민을 했고, 나는 무지 성 반복문을 돌리면 해결 가능하다고 생각했다. 하지만 매우 비효율적이라고 생각했고, 더 좋은 방법이 있을까 싶어 다른 사람들의 풀이를 찾아보았다.

 

정리하자면, 해당 알파벳이 나온 위치만큼을 계산해서 더한 후, 이를 내림차순으로 정렬하여 9부터 하나씩 할당해주면 된다. 위에 말했던 ABC CAB와 같은 문제가 그럼 깔끔하게 해결된다. A -> 110, C -> 101 이 되기 때문이다. 만약 둘 다 111 같이 나오는 경우가 발생하면 뭐가 먼저 되든 상관이 없기 때문에 신경 쓸 필요가 없다.

역시 답은 항상 간단하다.

 

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int arr[26];

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

    int answer = 0;
    int cnt = 9;
    for(int i=25; i>=0; i--) {
        if(arr[i] == 0) break;
        answer += arr[i] * cnt--;
    }
    cout << answer;
    return 0;
}

 

---

참고

https://mygumi.tistory.com/156

https://excited-hyun.tistory.com/145