[백준 1339] 단어 수학

문제 링크 => 1339번: 단어 수학 (acmicpc.net)

1339번: 단어 수학

 

그리디 알고리즘 문제이다.

 

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다.

이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다.

같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

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

 

알파벳에 숫자를 어떻게 부여할지에 대한 문제이다.

단순하게 생각한다면 9, 8, 7, ... 순서로 가장 긴 길이를 가진 문자열 순서로 접근할 수 있다.

그러나 문제점은 다음과 같다.

 

case 1 :  n = 10 / AB, B, B, B, B, B, B, B, B, B 인 경우

A = 9, B = 8 이라고 가정해보자.

그렇다면 A * 10 + (B + B + ... + B) = 90 + 80 = 170 이다.

그러나 식을 좀더 간단하게 정리해본다면 10*A + 10*B 으로 무조건 A + B값이 가장 크도록 배치해야 하며

A, B의 순서는 상관이 없다는 것을 알 수 있다.

 

case 2 : n = 10 / ABB, BB, BB, BB, BB, BB, BB, BB, BB, BB 인 경우

이번에도 A = 9, B = 8 이라고 가정해보자.

그렇다면 A * 100 + (BB + BB + ... + BB) = 900 + 880 = 1780 이다.

그러나 case 1처럼 식을 좀더 간단하게 정리해보면 100*A + 110*B 이다.

즉, A = 8, B = 9 일 때, 800 + 990 = 1790 으로 A = 9, B = 8 일 때보다 더 큰 결과값이 나타난다.

 

여기서 Greedy 한 접근이 필요한 것 같다.

B에 곱해진 숫자가 A에 곱해진 숫자보다 크므로 B값을 A보다 크게하면 무조건 큰 숫자를 만들 수 있다.

즉, 이 문제의 핵심은 case1, case2와 같이 식을 간단하게 정리하였을 때, 문자 앞에 곱해진 숫자에 따라 문자에

숫자를 어떻게 배정해야 할지에 대한 것이 문제이다.

 

예제를 하나 들어보도록 하자.

 

Result(before) = 1000A + 11000B + 1C + 111D + 100E + 1101F   

Result(after) = 11000B + 1101F + 1000A + 111D + 100E + 1C   

 

1. 위와 같이 정리한 식에 대해서 sorting algorithm을 활용한다.
2. 가장 큰 숫자에 곱해진 알파벳을 내림차순으로 9, 8, 7, ... 를 할당해준다.
3. 알파벳에 숫자를 부여하였으므로 모든 값을 합하여 결과를 리턴한다.

 

 

Solution code

 

#define _CRT_SECURE_NO_WARNINGS
#include <queue>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int value[26];
char X[10][26];

void initialize(int row, int col)
{
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			X[i][j] = '.';
		}
	}
}

bool compare1(string x, string y) {
	int x_size = x.size(), y_size = y.size();
	return x_size > y_size;
}

bool compare2(pair<char, int> x, pair<char, int> y) {
	return x.second > y.second;
}

int solution(vector<string> v)
{
	sort(v.begin(), v.end(), compare1);
	int row, maxLength, priority, result, op;
	vector<pair<char, int>> vv;

	row = v.size(), maxLength = v[0].size();
	initialize(row, maxLength);
	for (int i = 0; i < row; i++) {
		string s = v[i];
		int s_size = s.size();
		for (int j = 0; j < s_size; j++) {
			if (value[s[j] - 'A'] == 0) {
				vv.push_back({ s[j], 0 });
			}
			value[s[j] - 'A'] += pow(10, s_size - j - 1);
		}
	}

	for (int i = 0; i < vv.size(); i++) {
		vv[i].second = value[vv[i].first - 'A'];
	}

	sort(vv.begin(), vv.end(), compare2);
	priority = 9;
	for (int i = 0; i < vv.size(); i++) {
		value[vv[i].first - 'A'] = priority--;
	}

	result = 0;
	for (int i = 0; i < row; i++) {
		int tmp = 0;
		string s = v[i];
		int s_size = s.size();
		for (int j = 0; j < s_size; j++) {
			tmp += value[s[j]-'A'] * pow(10, s_size - j - 1);
		}
		result += tmp;
	}

	return result;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int N;
	vector<string> v;

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		v.push_back(s);
	}

	cout << solution(v);

	return 0;
}