백준 1339 - 단어 수학

C++

1339번 - 부등호

문제

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

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 문제 출처

접근 방법

완전 탐색이지만 Greedy로 생각하면 더 효율적이게 해결이 가능하다.
예제 입력 2를 사용하여 설명하면,
GCF는 100G + 10C + F 이며
ACDEB는 10000A + 1000C + 100D +10E + B 이다. 두개를 더하면 10000A, 1010C, 100G, 100D, 10C, F, B 가 되며, 큰 수부터 9~1을 배정하여 계산한다.

구현

alpha는 각 알파벳 자리를 뜻한다 따라서 26만큼의 크기로 배정하였다.
0은 A이고 1은 B…. 25는 Z 이런식으로 배정한다.
alpha[temp[j] - 'A'] 문자에 ‘A’ 만큼을 차감하면 아스키 코드로 인해 A~Z는 0~25로 각각 매핑이 된다. sort를 통해 정렬하여 각 알파벳의 수가 큰 수를 정렬하고, 앞에서 부터 9~1을 배정하여 단어의 합을 계산한다.

코드 - Back Tracking

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>

using namespace std;

int n;
long long result;
long long alpha[26];

bool comp(int a, int b) {		//오름차순을 위한 조건
	return a > b;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	string temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		for (int j = 0; j < temp.size(); j++) {
			alpha[temp[j] - 'A'] += pow(10, temp.size() - j - 1);
		}
	}
	sort(alpha, alpha + 26, comp);
	int idx = 9;
	for (int i = 0; i < 26; i++) {
		if (alpha[i] == 0)
			break;
		result += alpha[i] * idx;
		idx--;
	}
	cout << result;

	return 0;
}

후기 및 개선할 점