[그리디] 백준 1339 단어수학 C++

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

1339번: 단어 수학

---

---

풀이 :

 가장 긴 자리수를 가진 알파벳부터 순서대로 9, 8, 7 ... 이런식으로 대입해서 계산하면 된다.

그래서 각자리 수를 가진 배열을 따로 만들고.. 나름대로 방법을 적용했는데 실패해서 솔루션을 찾아본 문제

가장 긴 자리수를 어떻게 찾을까? -> 10의 거듭제곱을 사용하면 된다 예제에 나온대로 GCF + ACDEB 경우 각 자리수를 10의 거듭제곱을 이용해서 표현해보면 

GCF = 100*G + 10*C + F * 1( 1은 10의 0승이니까)

ACDEB = 10000*A + 1000*C + 100*D + 10*E + B

GCF + ACDEB = 10000A +1010C +100D + 100G + 10E + 10C + B + F

 

이렇게 내림차순 으로 정렬에해서 순서대로 9,8,7,6,5...... 대입해주면 된다. 이때 길이가 26이 되는 알파벳 배열을 만들어야하는데 alpaArr의 0번 인덱스는 A 자릿수 값, 1번 인덱스는 B의 자릿수 값 이렇게넣고 내림차순 으로 정리하면 문제에서 주어진 2번 예제 경우에

[10000, 1010, 100, 100, 10, 10, 1, ,1, 0......] 이렇게 될테니 0번이 나올 때까지 9,8,7... 이순서대로 대입해서 더해주면 된다! 

 

코드 : 

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

using namespace std;
int n;
string s;
int alpaArr[27] = { 0, };
vector<string> strVec;
bool desc(int a, int b) {
	return a > b;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		strVec.push_back(s);
	}

	for (string str : strVec) {
		int len = str.length();
		int tmp = 0;
		for (int i = 0; i < len; i++) {
			int arrNum = str[i] - 'A';
			alpaArr[arrNum] += pow(10, (len - i)-1);
			tmp++;
		}
	}
	sort(alpaArr, alpaArr + 27, desc);
	int ans = 0;
	int tmp = 9;
	for (int i = 0; i < 27; i++) {
		if (alpaArr == 0) break;
		ans += tmp * alpaArr[i];
		tmp--;
	}
	cout << ans << endl;

	

}