[백준 1339] 단어수학(C++)

📕문제

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

단어 수학 문제는 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초 만에 틀렸습니다가 나오길래 굉장히 당황했었다. 내가 놓친 부분이 있던가? 

그렇게 해서 다시 고민을 해보니까 내가 놓친 점이 있었다.

예를 들어서 ABC, BB, BB, BB, BB, BB, BB, BB, BB, BB 10개의 input이 주어졌을 때,

내가 짠 알고리즘은 A에서는 A=9, B=8, C=7을 할당할 것이다. 하지만 이렇게 할당하는 것이 과연 최대일까?

정답은 아니다.

나의 알고리즘 : 987 + 88 *9 =  1779이다.

개선 알고리즘은 각 문자가 뜻하는 숫자를 10의 n승 단위로 표현한다.

ABC에서 A는 10^2, B는 10^1, C는 10^0이다.

이렇게 전체 입력받은 문자열마다 숫자를 대응시킨다.

이렇게 되면 A는 100을 의미하지만 B는 11*9 + 10 =109를 의미한다.

이 뜻은 A가 B보다 자릿수가 높지만, 실제로 표현하는 수는 B가 A보다 더 큰 수를 표현한다는 뜻이다.

따라서 나는 각 문자열마다 표현 가능한 숫자를 대응시키고, 큰 순서대로 숫자를 할당했다.

이렇게 개선한 알고리즘으로 계산을 하면

개선 알고리즘 : 897 + 99*9 = 1788이다.

이제 자세한 설명은 세부 코드 설명으로 하겠다.

---

구현

1. 변수 선언

• voca는 input에서 주어지는 문자열을 저장하는 vector
• bulk는 주어지는 문자열의 길이를 저장하는 vector이다.
• pair p과 m는 각 문자열에서 문자마다 표현할 수 있는 수의 범위를 저장함. (10^n, 문자)
• ans_string은 이제 문자열을 숫자로 바꿔준 것을 저장. (stoi를 통해 나중에 계산함)
• result는 이제 모든 문자열에 대해서 표현할 수 있는 범위를 저장함.

2. 문자열 입력과 크기 저장.

3. 문자열의 크기순 서대로 내림차순 정렬

4. 각 문자열을 가장 큰 size로 강제로 늘려줌. (늘려준 공간은 빈 공간으로 처리)

• 이렇게 늘려준 이유는 자릿수를 일치시켜주기 위해서이다.
  • 예를 들어 ABCDE와 DEF가 있을 때 배열에는 똑같이 A와 D는 0번지에 들어가게 된다. 하지만 A와 D는 다른 자리의 숫자이다. 그것을 구분시켜주기 위해서 강제로 늘리고 빈 공간에 'a'를 넣어서 공백으로 처리했다.
  • 대문자만 입력받기 때문에 소문자는 자동으로 예외처리가 될 것이다.

5. 각 문자마다 표현할 수 있는 숫자를 저장.

• 모든 문자열에 대해서 숫자를 저장함.
  • ABCDE에서 A는 0번지이지만 5번째 자릿수이기 때문에 10^4이 저장되어야 함.
  • 그래서 저런 식으로 표현했음.

6.map에다 전체 문자에 대한 우선순위를 정해줌.

• 입력받은 모든 문자열에서 문자들을 추출해서 우선순위를 정함.
  • 그 방법은 이제 각 문자가 표현할 수 있는 수의 범위를 저장.
  • 이미 map에 저장되어있다면 value를 업데이트시켜줌.

7. 표현할 수 있는 수의 범위가 큰 순서대로 정렬함.

8.map에다 우선순위가 높은 순서대로 9~0까지 할당해줌. 

9. 각 문자가 뜻하는 숫자를 문자열로 쭉 표현해서 더해줌.

 

 

📜코드

// 백준 1339 골드4 단어수학
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
#include <string>
using namespace std;
int n;
vector<string> voca;
vector<int> bulk;
vector<pair<int, char>> p;
map<char, int> m;
vector<string> ans_string;
vector<pair<int, char>> result;
bool comp(int a, int b)
{
    return a > b;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        voca.push_back(s);
        bulk.push_back(voca[i].size()); //입력받은 문쟈열의 길이를 배열에 저장함.
    }
    for (int i = 0; i < n; i++) //문자열의 크기순서 대로 배열을 정렬.이러면 배열의 첫 원소가 가장 긴 문자열일거임.
    {
        for (int j = i + 1; j < n; j++)
        {
            if (bulk[i] < bulk[j])
            {
                swap(bulk[i], bulk[j]);
                swap(voca[i], voca[j]);
            }
        }
    }
    for (int i = 1; i < n; i++)
    {
        string s = voca[i];
        voca[i].erase();
        int Size = bulk[0] - bulk[i]; //가장 긴 문자열을 기준으로 각 문자열과의 차이만큼 빈 공간을 만들어줌.
        // cout<<Size<<endl;
        int idx = 0;
        while (idx != Size)
        {
            // cout<<1<<endl;
            voca[i] += "a"; //아무문자나 넣은것임. 어차피 입력문자는 대문자라 소문자는 상관없음!
            idx++;
        }
        voca[i] += s; //공백을 포함한 문자열 완성
    }
    int Max_size = voca[0].size(); //가장 긴 문자열의 길이를 변수로 저장해둠. 계속 입력하기 귀찮음.
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < Max_size; j++)
        {
            p.push_back(make_pair(pow(10, Max_size - j - 1), voca[i][j]));
            //각 문자별로 위치한 자리를 10의 지수로 나타냄. 예를 들어 ABCDE면 A는 10의 4승, B는 10의 3승 이렇게..
        }
    }
    sort(p.begin(), p.end());
    // pair 의 first는 자리수, second는문자
    // map의 첫번쨰는 문자, second는 숫자
    for (int i = 0; i < p.size(); i++)
    {
        if (p[i].second == 'a') //내가 임시로 만들어준 공간이면 넘어감.
        {
            continue;
        }
        else
        {
            if (m.find(p[i].second) == m.end()) //처음 map에 넣는다면 그냥 그 문자가 가지는 숫자를 넣어줌.
            {
                m.insert(make_pair(p[i].second, p[i].first));
            }
            else
            { //찾앗다면? 원래 기존의 숫자와 더해줌. EX) ABBCE 면 B는 1000과 100을 나타냄. 따라서 map에는 1100이 저장되야함.
                int value = m.find(p[i].second)->second;
                m[p[i].second] = value + p[i].first;
            }
        }
    }

    // result안에 각 문자와 그 문자가 표현하는 수를 넣어줌. EX) A 10000, B 1010
    for (auto iter = m.begin(); iter != m.end(); iter++)
    {
        result.push_back(make_pair(iter->second, iter->first));
    }
    for (int i = 0; i < result.size(); i++)
    {
        for (int j = i + 1; j < result.size(); j++)
        {
            if (result[i].first < result[j].first) //자리수가 큰 순서대로 정렬함.
            {
                swap(result[i], result[j]);
            }
        }
    }
    m.clear();
    //문자열을 이제 숫자로 매핑해야함.
    int answer = 9; //각 알파벳은 0~9까지의 숫자를 표현할 수 있음. 우선순위가 높은 순서대로 9,8,7 ... 이렇게 할당함.
    for (int i = 0; i < result.size(); i++)
    {
        if (m.find(result[i].second) == m.end()) //각 알파벳의 숫자를 넣어줌. 9~0
        {
            m.insert(make_pair(result[i].second, answer));
            answer--; //한번 넣어준 숫자는 못넣기 때문에 감소시켜줌.
        }
    }
    for (int i = 0; i < n; i++)
    {
        string s;
        for (int j = 0; j < Max_size; j++)
        {
            int num = m.find(voca[i][j])->second;
            s += to_string(num);
        }
        ans_string.push_back(s);
    }
    int sum = 0;
    for (auto a : ans_string)
    {
        int num = stoi(a);
        sum += num;
    }
    cout << sum;
}

---

👀느낀 점

• greedy 하게 푼다는 방법이 이제 감이 잡히는 것 같다.
• 이 문제는 반례를 생각하는 것이 조금 어려웠지, 알고리즘 짜는 것 자체는 어렵지 않았다.
• 조금 지저분하게 짠 것 같다. pair와 map을 둘 다 사용했으니..
• 그래도 처음 의도한 알고리즘에서 조금만 개선해서 풀어서 굉장히 기분이 좋다