[BOJ] 1339 단어 수학 with C++

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

1339번: 단어 수학

 

이 글은 BOJ 1339 단어 수학 문제를 C++로 풀이한 글입니다.

 

풀이

처음 문제를 봤을 때 어떻게 풀어야 할 지 바로 감이 오는 문제는 아니었다.

문제 풀이 방법이 떠오르지 않을 때 쓸수 있는 자료구조를 고민해 보고 모든 경우의 수를 다 고려하는 브루트 포스로 해결가능 한지 먼저 고려해 보는 편인데, 해당 문제의 경우 하나의 숫자는 하나의 알파벳이랑만 매칭되고 또한 주어지는 단어의 개수가 최대 10이고 단어의 단어의 길이가 최대 8자라는 조건이 붙어 있는것을 확인했다.

 

중복 허용하지 않고 알파벳 하나당 하나의 숫자만 맵핑이 된다면 알파벳은 최대 10개가 주어지고 단어는 8자리를 넘지 않으면서 10개이므로 이를 숫자로 변환해 더할 때 또한 int 범위를 벗어나지 않는다는 것을 확인 한 후 보니 경우의 수가 작을 것이란 생각이 들었다. 

 

알파벳이 최대 10개까지 주어질테고 이를 0~9까지의 수로 맵핑하는 것이므로 10! 개 만큼의 경우의 수가 필요한데 이는 약 360만 으로 2초의 시간내로 충분히 결정지을 수 있는 경우의 수이고 알파벳의 숫자만 결정된다면 계산하는 것은 단어가 10개 밖에 안되므로 굉장히 빠른 속도로 처리가 가능할 것이 분명하여 브루트 포스로 해결하기로 결정했다.

 

문제에서 결과의 최대값을 반환하도록 하였으므로 알파벳이 숫자가 큰게 많이 사용될 수록 유리하므로 큰 숫자부터 차례대로 결정하는 방식으로 진행한다.

 

value 라는 배열을 선언해 A의 경우 0, Z의 경우 25 인덱스가 해당 알파벳의 값이 되도록 진행하고 결정한 값을 넣어준 후 모든 값을 주어진 단어를 숫자로 변환하여 값을 계산하고 매번 최대값으로 갱신해준다.

코드

/**
 * https://www.acmicpc.net/problem/1339
 *
 * solution: 브루트 포스(Brute Force)
 * 알파벳 최대 10개를 중복 없이 0 ~ 9 까지를 부여하는 경우의 수는
 * 10! -> 약 360만 시간제한 2초로 충분히 해결가능한 범위
 * 모든 경우를 순회하며, 최대값을 찾아 반환한다.
 */
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int n, ans;
string word[10];
vector<char> alphabet;
bool visited[10] = {0};
int value[26];

int calculate()
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        int res = 0;
        for (int j = 0; j < word[i].size(); j++)
            res = res * 10 + value[word[i][j] - 'A'];
        sum += res;
    }
    return sum;
}

void solve(int idx)
{
    if (idx == alphabet.size())
    {
        ans = max(ans, calculate());
        return;
    }

    for (int i = 9; i > 9 - static_cast<int>(alphabet.size()); i--)
    {
        if (visited[i])
            continue;
        value[alphabet[idx] - 'A'] = i;
        visited[i] = true;
        solve(idx + 1);
        value[alphabet[idx] - 'A'] = 0;
        visited[i] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> word[i];
        for (int j = 0; j < word[i].size(); j++)
            alphabet.push_back(word[i][j]);
    }
    sort(alphabet.begin(), alphabet.end());
    alphabet.erase(unique(alphabet.begin(), alphabet.end()), alphabet.end());

    solve(0);
    cout << ans;
    return 0;
}