[백준 1339번 C/C++] 단어 수학

 

[백준 1339번 C/C++] 단어 수학

 

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

1339번: 단어 수학

---

 

해결전략

 

탐욕법 Greedy Algorithm 그리디 알고리즘

 

각 알파벳

 

[ 예제 ]

2

GCF

ACDEB

 

G=100 C=10 F=1                               -> GCF = 100G + 10C + 1F

A =10000 C=1000 D=100 E=10 B=1 -> ACDEB = 10000A + 1000C + 100D + 10E + 1B

 

A = 10000 * 9

C = 1010 * 8

D = 100 * 7

G = 100 * 6

E = 10 * 5

F = 1 * 4

B = 1 * 3

 

ACDEB + GCF = 99437

---

 

정답 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int n;
vector<string> word;  // 입력 받을 단어들
map<char, int> myMap; // key: 알파벳, value: 알파벳에 대응하는 숫자

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

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

	cin >> n;
	word.resize(n);
	for(int i=0; i<n; i++){
		cin >> word[i];

		int m = word[i].size();
		for(int j = 0; j < m; j++)
		{
			if (myMap.find(word[i][j]) != myMap.end())
				myMap[word[i][j]] += pow(10, (m - 1) - j);
			else
				myMap.insert({word[i][j], pow(10, (m-1) - j)});
		}
	}

	// myMap의 모든 요소를 벡터 v에 삽입한 후, Compare 함수를 이용해 내림차순으로 정렬
	vector<pair<char, int>> v;
	for(const auto& iter : myMap){
		v.push_back(iter);
	}
	sort(v.begin(), v.end(), Compare);

	//for (const auto& iter : v)
	//	cout << iter.first << " " << iter.second << "\n";

	// 가장 큰 값을 가지는 문자부터 9부터 시작해 1씩 줄어드는 숫자를 곱하여 answer에 더한다. 이는 가장 가치가 높은 문자부터 가장 높은 숫자를 할당하는 것이다.
	int answer = 0;
	int number = 9;
	for(int i = 0; i < v.size(); i++)
	{
		answer += v[i].second * number;
		number--;
	}

	cout << answer << "\n";

	return 0;
}

 

 

---