백준 1339. 단어 수학

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

1339번: 단어 수학

 

처음에 바로 생각난 방법은 브루트포스를 이용한 방법이다.

각각의 알파벳에 가능한 모든 경우의 수의 숫자들을 할당하고 더해서 최댓값을 찾는다.

이방법은 시간초과가 날것같긴 했으나 오랜만에 브루트포스 방식으로 풀어보고 싶어서 풀어봤고 역시 시간초과가 났다.

---

다음에 생각난것은 각 문자열의 열들을 비교하는 방법이다.

우선 가장 앞에 있는 열부터 높은 숫자를 할당하고 같은 열에 대해서는 높은 열에 더 많은 갯수가 있는 알파뱃부터 높은 숫자를 할당한다.

이 방법은 다음과 같은 입력이 들어왔을때 실패했다

2

AA

BC

내가 생각한 알고리즘 대로라면 A,B둘중 A를 9를 줘도 되고, B를 9를 줘도 되는데, 

이경우에는 뒷자리에도 A가 또 있어서 A에 9를 줘야 정답이다.

---

마지막으로 정답처리 받은것은 가장 아래 자리부터 10^1, 10^2 ... 로 점수를 주는 방식이다.

입력이 다음과 같다면 

2

AB

BA

 

제일 아래자리에 B,A가 있는데 B에 10, A에 10점을 준다.

다음 자리에 A,B가 있는데 A에 10^2, B에 10^2점을 준다.

A는 총 10+10^2 = 110

B는 총 10^2+10 = 110 으로 둘이 점수가 같으므로 이 경우에는 두 알파벳은 9,8중 아무 숫자나 줘도된다.

 

 

 

 

실패한것들:

시간초과:

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

int n;
int ans = 0;
//string a,b;
string str[10];
string temp;
int alp[26];

vector<int> v;

int Add()
{
    int sum = 0;
    string to_str[10];

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < str[i].size(); j++)
        {
            to_str[i] += to_string(alp[str[i][j]-65]);
        }
    }

    for(int i = 0; i < n; i++)
    {
        sum += stoi(to_str[i]);
    }

    return sum;
}

void InitAlp()
{
    for(int i = 0; i < 26; i++)
        alp[i] = 0;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> str[i];
        temp += str[i];
    }

    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(),temp.end()), temp.end());


    int num = 9;
    for(int i = 0; i < temp.size(); i++)
    {
        v.push_back(num--);
    }

    do {

        InitAlp();
        for(int i = 0; i < temp.size(); i++)
        {
            alp[temp[i]-65] = v[i];
        }


        ans = max(ans, Add());

    }while(prev_permutation(v.begin(),v.end()));

    cout << ans;



}

---

 

예외 발생:

2

AA

BC

 

답: 186

출력: 185 

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

int n;
string str[10];
int maxSize = 0;
int alp[26];
int alp_cnt[26];
int num = 9;

void AlpCntInit()
{
    for(int i = 0; i < 26; i++)
        alp_cnt[i] = 0;
}

long long Cal()
{
   long long sum = 0;
   string to_str[10];

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < str[i].size(); j++)
        {
            to_str[i] += to_string(alp[str[i][j]-65]);
        }
    }
    cout << "MADE STRING" << endl;
    for(int i = 0; i < n; i++)
    {
        cout << to_str[i] << endl;
    }


    for(int i = 0; i < n; i++)
    {
        sum += stoi(to_str[i]);
    }

    return sum;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> str[i];
        maxSize = max(maxSize, (int)str[i].size());
    }

    for(int i = 0; i < n; i++)
    {
        // 최대 길이 문자열보다 작으면 앞을 'a'로 채워넣음
        if(str[i].size() < maxSize)
        {
            int count = maxSize - (int)str[i].size();

            for(int j = 0; j < count; j++)
            {
                str[i] = "a" + str[i];
            }
        }
    }


    for(int i = 0; i < maxSize; i++)
    {
        vector<char> v;
        for(int j = 0; j < n; j++)
        {
            // 해당 알파벳이 숫자 할당 아직 안됐다면
            if(str[j][i] != 'a' && alp[str[j][i]-65] == 0)
            {
                v.push_back(str[j][i]);
            }
        }

        AlpCntInit();
        for(int j = 0; j < v.size(); j++)
        {
            alp_cnt[v[j]-65]++;
        }

        int maxCnt = 0;
        int maxCntIdx = 0;
        for(int j = 0; j < 26; j++)
        {
            if(alp_cnt[j] == 0) continue;
            if(alp_cnt[j] > maxCnt)
            {
                maxCnt = alp_cnt[j];
                maxCntIdx = j;
            }
        }

        // 갯수, 알파벳
        vector<pair<int,char>> set;
        for(int j = 0; j < 26; j++)
        {
            if(alp_cnt[j] == 0) continue;
            set.push_back({alp_cnt[j], (char)(65+j)});
        }
        // 갯수 기준 내림차순
        sort(set.begin(), set.end(), greater<>());

        for(int j = 0; j < set.size(); j++)
        {
            alp[set[j].second-65] = num--;
        }
    }

    for(int i = 0; i < 26; i++)
        cout << alp[i] << ' ';
    cout << endl;

    cout << Cal();

}

 

 

정답: