백준 - 단어 수학 (1339) [C++]

이 문제는 그리디 알고리즘으로 풀었다.

 

완전 탐색으로 가능해 보이지만, 직접 코드를 작성해보니 시간 초과가 났다.

 

각 단어에서 알파벳을 검사하고, 해당 위치에 대해 가중치를 10^n 단위로 매겼다. 이를 각 알파벳에 더해주고, 해당 가중치로 내림차순 정렬하여 순서대로 9부터 숫자를 매겼다. 이 방법으로 정답을 맞출 수 있었다.

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>

using namespace std;

#define MAX 10
#define ALPHA 26

int N;
string words[MAX];

map<char, int> cost;
map<char, char> mappedNum;

int calcPower(int power) {
	if (power == 0) {
		return 1;
	}
 	return 10 * calcPower(power - 1);
}

bool compare(pair<char, int> &a, pair<char, int> &b) {
	return a.second > b.second;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> words[i];
	}

	for (int i = 0; i < N; i++) {
		string& word = words[i];
		
		int wordSize = word.size();
		for (int j = 0; j < wordSize; j++) {
			char c = word[j];

			int power = wordSize - j - 1;
			int presentCost = calcPower(power);
			cost[c] += presentCost;
		}
	}

	vector<pair<char, int>> alpha;
	for (auto iter = cost.begin(); iter != cost.end(); iter++) {
		char key = iter->first;
		int tempCost = iter->second;

		alpha.push_back({ key, tempCost });
	}

	sort(alpha.begin(), alpha.end(), compare);

	char num = '9';
	for (int i = 0; i < alpha.size(); i++) {
		char c = alpha[i].first;
		char num = (char)((9 - i) + '0');
		mappedNum[c] = num;
	}

	int answer = 0;
	for (int i = 0; i < N; i++) {
		string &word = words[i];

		string temp = "";
		for (char c : word) {
			temp += mappedNum[c];
		}

		answer += stoi(temp);
	}

	cout << answer << '\n';

	return 0;
}