[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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

 

출력

첫째 줄에 모든 수의 최대 합을 출력한다. 

 

---

풀이 과정

처음에는 자릿수가 가장 많은 순서대로 단어들을 정렬한 후 0번째 인덱스에 있는 단어부터 한 글자씩 숫자로 바꿔간 후 1번째 인덱스부터 만나는 단어들 중 숫자로 바꾼 적이 있는 단어를 바꿔주고 그렇지 않으면 숫자로 바꿔주고를 반복하면 될 것이라 생각했습니다. 

하지만 예제 2번을 통과하지 못 했기 때문에 힌트를 찾아 보았고... 제 접근 방법 자체가 틀렸다는 것을 알았습니다.

그래서 수정한 접근 방법

 

1. 입력받으면서 각 알파벳별로 갯수를 저장하는데, (pair 구조체 사용)

입력이 ABC 라고 주어진다면 A는 100개, B는 10개, C는 1개가 있는 것이라 계산한다. 

 

2. 1번 과정을 거쳐서 저장된 pair<알파벳, 갯수> 들을 내림차순으로 정렬한다. 

 

3. 반복문으로 0번째 인덱스의 갯수에 9를 곱하고 

1번째 인덱스의 갯수에 8을 곱한 값을 아까 구했던 값에 더하고... 를 배열 인덱스가 끝날 때까지 반복한다. 

 

---

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

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<pair<char, int>> words;
    for (int i = 0; N > i; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; str.length() > j; j++)
        {
            int len = str.length() - j - 1;
            
            char ch = str[j];
            auto it = find_if(words.begin(), words.end(), 
            [&ch](const pair<char, int>& elem){ return elem.first == ch; });
            
            //현재 알파벳의 자릿수만큼 10을 제곱한 값을 저장한다. 
            if (words.end() == it)
                words.emplace_back(make_pair(ch, pow(10, len)));
            else
                it->second += pow(10, len);
        }
    }
    
    //갯수가 많은 순서대로 내림차순 정렬 
    sort(words.begin(), words.end(), 
    [](const pair<char, int>& a, pair<char, int>& b)->bool { return a.second > b.second; });
    
    long answer = 0;
    int exchangeNum = 9; //9부터 하나씩 줄여가며 누적합계를 구함 
    for (int i = 0; words.size() > i; i++)
        answer += words[i].second * exchangeNum--;
    
    cout << answer;
    
    return 0;
}