1339_단어 수학

▶골드4

 

문제

 

풀이

이 문제는 문자 간의 우선순위를 정하는게 중요한 문제였다.

주어진 문자들 중에서 가장 큰 자릿수를 가진 문자가 가장 큰 수를 부여받고, 그 다음 큰 자릿수를 가진 문자가 그 다음 큰 수를 부여받고.... 이런 순으로 주어진 모든 문자에 숫자가 할당되면 이를 더하고 값을 출력한다.

 

처음에는 어렵게 생각해서 문자열이 긴 순으로 저장하고 문자를 할당하는 map을 따로 만들어서 할당 여부를 확인하고...뭐 이런식으로 진행했는데 너무 비효율적인 방법이었다.

 

자릿수를 생각하지 않아도 되도록 주어진 알파벳의 번호에 해당하는 인덱스 배열에 자릿수에 해당하는 값을 더한다.

ex) ACDB -> 1320(거꾸로) -> alpha[0] = 1, alpha[2] = 10, alpha[3] = 100, alpha[1] = 1000 

이런식으로 할당하면 문자의 우선순위를 알 수 있다.

모두 진행하고 나면 우선순위가 높은 순으로 배열에 주어진 값과 부여받은 숫자를 곱하여 결과 값에 더한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
using namespace std;

int alpha[26];

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

	int n;
	cin >> n;

	
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		int now = 1;
		for (int j = str.length() - 1; j >= 0; j--) {
			alpha[str[j] - 'A'] += now;
			now *= 10;
		}

	}

	sort(alpha, alpha + 26);

	int num = 9;
	int ans = 0;
	for (int i = 25; i >= 0; i--) {
		ans += (alpha[i] * num);
		num--;
	}
	cout << ans;
}