백준1339 - 단어 수학

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

1339번: 단어 수학

하루 걸려서 풀었다. 처음에 숫자 출현 빈도수로 풀었다가 틀려서 인터넷을 찾아보고 힌트를 얻게 되었다. 수식으로 풀어서 알파벳마다 가중치를 모두 더한 뒤 9부터 가중치가 큰 것에 곱하여 결과를 도출하면 되었다. 가중치가 내려가면 -1을 하여 곱한다.

 

ex1.)

ABCD

BCE

 

ABCD = 1000A + 100B + 10C + 1D

BCE = 100B + 10C + 1E

ABCD + BCE : 1000A + 200B + 10C + 1D + 1E

 

가중치 내림차순으로 만든 뒤 숫자 부여한 결과 : A B C D E -> 9 8 7 6 5

 

 

 

ex2.)

ABC

BCD

CAE

 

ABC = 100A + 10B + 1C

BCD = 100B + 10C + 1D

CAE = 100C + 10A + 1E

 

ABC + BCD + CAE = 110A + 110B + 111C + 1D + 1E

 

가중치 내림차순으로 만든 뒤 숫자 부여한 결과 : C B A D E -> 9 8 7 6 5

 

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

int main() {
	int n; //수행 횟수
	int input = 9; //9부터 들어가서 -1씩 줄어든다.
	long long int sum = 0; //결과
	vector<int> v; //맵의 value만을 저장
	map<char, int> mp; //각 문자에 대한 숫자의 자릿수(가중치)를 저장
	string s; //숫자

	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> s;
		reverse(s.begin(), s.end()); //거꾸로 배치하면 가장 작은 수의 인덱스가 가장 작다.
		for (unsigned int i = 0; i < s.size(); i++) {
			if (mp.find(s[i]) == mp.end()) { //key가 없으면
				mp[s[i]] = pow(10, i); //key에 해당하는 value를 설정
			}
			else { //key가 존재하면
				mp[s[i]] = mp[s[i]] + pow(10, i); //이미 있던 value에 현재 자릿수(가중치)를 더한다.
			}
		}
	}

	//value값만 vector에 삽입
	map<char, int>::iterator iter;
	for (iter = mp.begin(); iter != mp.end(); iter++) {
		v.push_back(iter->second);
	}

	sort(v.begin(), v.end(), greater<int>()); //내림차순 배열

	//가중치(자릿수를 더한 것)에 9부터 차례로 -1을 곱한 후 sum에 더한다.
	for (unsigned int i = 0; i < v.size(); i++) {
		sum = sum + v[i] * input;
		input--;
	}

	cout << sum;
}