백준 1339 단어 수학

초등학교때 많이 보던 문제를 컴퓨터를 가지고 해결해보는 문제이다. 최대 10종류의 알파벳 대문자로 이루어진 단어를 숫자로 생각하고, 그 숫자들의 합이 최대가 될 때의 값을 구한다.

 

처음 접근했을때는, DFS 검색으로 조합들을 검색했다. 단어들을 구성하는 문자가 7개라면, 7!의 경우의 수 공간을 탐색하면서 최대값을 찾았다. -> 답은 나왔지만 시간초과가 떴다.

 

두번째 접근은, 그리디로 접근했다. 각 문자별로 자리수의 합을 구해서 높은 자리수에 많이 있는 숫자부터 높은 수를 할당해줬다. ABC + ACB = 2*A*100 + B*10 + C*10 + C + B이므로, A의 자리수 합은 200이 된다. 이렇게 각 문자의 자리수 합을 구한 뒤, 높은것부터 높은 수를 할당해서 계산해보니 답이 딱 나왔다.

중간에 배열과 그냥 int 벡터로 하기에 너무 귀찮아서 각 문자의 자리수와 할당된 숫자를 같이 저장하는 구조체를 만들었고, 구조체를 활용해서 정렬하고 탐색하니까 훨씬 코드가 간편해졌다.

---

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

std::vector<std::string> word_list;
std::vector<char> letter_list;

// int dfs(std::vector<int> num_list)
// {
//     int ret = 0;
//     if (num_list.size() == letter_list.size())
//     {
//         for (std::string word : word_list)
//         {
//             int number = 0;
//             for (char c : word)
//             {
//                 number *= 10;
//                 number += num_list[std::find(letter_list.begin(), letter_list.end(), c) - letter_list.begin()];
//             }
//             ret += number;
//         }
//         // for (int i : num_list)
//         //     std::cout << i << " ";
//         // std::cout << '\n';
//         return ret;
//     }
//     else
//     {
//         for (int i = 0; i < 10; i++)
//         {
//             if (num_list.size() && std::find(num_list.begin(), num_list.end(), i) != num_list.end())
//                 continue;
//             num_list.push_back(i);
//             ret = std::max(dfs(num_list), ret);
//             num_list.pop_back();
//         }
//         return ret;
//     }
// }
typedef struct {
    char c;
    int prio;
    int val;
} t_char;

bool comp_prio(t_char t1, t_char t2)
{
    return(t1.prio > t2.prio);
}

bool comp_char(t_char t1, t_char t2)
{
    return(t1.c < t2.c);
}

int main()
{
    int n;
    // std::vector<std::string> word_list;
    // std::vector<char> letter_list;
    std::vector<t_char> char_list;
    std::cin >> n;

    for (int i = 0; i < 26; i++)
    {
        t_char tmp = {'A' + i, 0, 0};
        char_list.push_back(tmp);
    }
    for (int i = 0; i < n; i++)
    {
        std::string tmp;
        std::cin >> tmp;
        for (int j = 0 ; j < tmp.size(); j++)
        {
            // if (letter_mask[c - 'A'] == false)
            // {
            //     letter_mask[c - 'A'] = true;
            //     letter_list.push_back(c);
            // }
            // char_list[tmp[j] - 'A'].prio  = std::max(char_list[tmp[j] - 'A'].prio, (int)tmp.size() - j);
            char_list[tmp[j] - 'A'].prio += std::pow(10, (int)tmp.size() - j - 1);
        }
        word_list.push_back(tmp);
    }
    std::sort(char_list.begin(), char_list.end(), comp_prio);
    for (int i = 9; i >= 0; i--)
    {
        char_list[9 - i].val = i;
    }
    std::sort(char_list.begin(), char_list.end(), comp_char);
    int ret = 0;
    for (std::string word : word_list)
    {
        int number = 0;
        for (char c : word)
        {
            number *= 10;
            number += char_list[c - 'A'].val;
        }
        ret += number;
    }
    // for (auto c : letter_mask)
    // {
    //     std::cout << c << " ";
    // }
    // std::vector<int> temp;
    std::cout << ret;
}

 

코드 겁나 긴데, DFS 탐색 코드를 전부 주석처리 해뒀다. 따로 구조체 만들어서 쓰는게 귀찮긴 한데 한번 만들어두면 편하긴 하네...

 

오늘도 평온한 하루가 되길. 슨민.