[ 백준-1339번 / 백트래킹, 브루트 포스, DP ] 단어수학

1. 문제

---

문제

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

단어 수학 문제는 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 복사

2 AAA AAA

예제 출력 1 복사

1998

 

 

2. 소스코드

---

1회차 - 2020/06/04

 

- vector에 중복없이 알파벳을 입력받고, vector의 인덱스를 0~9를 숫자로 매칭해서 모든 경우의 수의 답을 구하려했다.

- 단, 치환 값은 9 - idx, (숫자는 0~9까지이고, 최대값을 구해야하므로 당연히 높은 숫자부터 매칭해야한다)

예를 들어 vector[1] = 'A' 이면 A는 숫자 8인셈.

 

- 그리고 이를 next_permutation을 통해, 모든 경우를 탐색하려했으나....

다음 예제에서 시간 초과가 나왔다!

 

10
A B C D E F G H I J

 

- 최대 단어는 10개, 최대 알파벳도 10개이다.

- next_permutation의 모든 경우의 수는 10! * 10 =  36,288,000‬. 4천만 정도밖에 안되는데, 시간 초과를 받았다.

 

문제의 소스 코드

#pragma warning (disable : 4996)
#include <cstdio> 
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <math.h>
#define MAX 8
using namespace std;
int n, ans;
char word[MAX + 2][MAX];
vector<char> ch;
 
int main() {
    ch.reserve(10);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf(" %s", word[i]);
        for (int j = 0; j < strlen(word[i]); ++j) {
            ch.push_back(word[i][j]);
        }
    }//중복없이 입력을 받음.
    sort(ch.begin(), ch.end());
    ch.erase(unique(ch.begin(), ch.end()), ch.end());
    
    do {
         map<char, int> hash;
        for (int i = 0; i < ch.size(); ++i) {
            hash.insert({ch[i], 9 - i });
        }
        
        //환산을 시작한다.
        int res = 0;
        for (int i = 0; i < n; ++i) {
            //하나의 단어를
            for (int j = 0; j < strlen(word[i]); ++j) {
              res += (hash.find(word[i][j])->second) * pow(10, strlen(word[i])-1-j);
            }
        }
        if (res > ans) ans = res;
         

    } while (next_permutation(ch.begin(), ch.end()));
    printf("%d", ans);
    return 0;
}

 

- 아무래도 원인은 2가지 중 하나일 것 같다.

1) map을 사용한 것

2) pow를 사용한 것

 

- map의 연산은 상수 시간이 아니다. O(logN) 이다. { 최악의 경우, 최대 단어 수와, 최대 글자 수는 같다 }

- 그럼 매번 map을 구성하는데만, 약 O(NlogN)이 걸리고, { 최대 글자 수 x map시간복잡도 }

- map을 참조해서 값을 구하는 대에도, 약 O(N * (N-2) * logN) { 최대 단어 수 x 최대 단어길이 수 x map시간복잡도 }

- 정리하면, 하나의 경우의 수 연산에 O(N^2logN)이다.

- 물론 N이 10으로 매우 작지만, 10! x 10 x O(N^2logN)이 40억은 가뿐히 넘을 것이다.
 

-  pow연산이 그렇게 크지 않다고 생각했는데, 역시 경우의 수가 크면 pow연산으로 인한 속도 저하가 눈에 띄게 나타났다.

- vector로 map을 대체한 뒤에도 pow를 이용한 경우, 시간초과가 났다.

 

- 결국, map pow 둘 모두다 사용하면 안되었던 것.

 

 

 

개선한 코드

- 다만, 이 코드도 백트래킹, 그리디 알고리즘을 전혀 쓰지 않았다. 순수 브루트 포스로 푼셈.

- 브루트 포스가 아닌 다른 알고리즘을 이용할 경우, map or pow를 사용해도 시간 내에 수행될 수 도 있다.

#pragma warning (disable : 4996)
#include <cstdio> 
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX 9 // \n 공간까지 고려해야한다
using namespace std;
int n, ans;
char word[MAX + 2][MAX];
vector<char> ch;
 
int main() {
    ch.reserve(10);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf(" %s", word[i]);
        for (int j = 0; j < strlen(word[i]); ++j) {
            ch.push_back(word[i][j]);
        }
    } 

    sort(ch.begin(), ch.end());
    ch.erase(unique(ch.begin(), ch.end()), ch.end());
    
    vector<int> digit(ch.size());
    for (int i = 0; i < digit.size(); ++i) 
        digit[i] = 9 - i;
 
    vector<int> hash(26);

    int m = ch.size();
    do {
        for (int i = 0; i < m; ++i)
            hash[ch[i] - 'A'] = digit[i];
 
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            int len = strlen(word[i]);
            int res = 0;
            for (int j = 0; j < len; ++j) {
                res = res * 10 + hash[word[i][j] - 'A'];
            }
            sum += res;
        }
        if (sum > ans) ans = sum;

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

    printf("%d", ans);
    return 0;
}