백준 1339 단어 수학(c++)

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

1339번: 단어 수학

<코드>

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

int main()
{
	string s;
	int n;
	cin>>n;
	vector<int>alpha(26);
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		for(int j=0;j<s.size();j++)
		{
			alpha[s[j]-'A']+=pow(10,(s.size()-1)-j);
		}
	}
	sort(alpha.rbegin(),alpha.rend()); //내림차순 정렬
	int num=9;
	int sum=0;
	for(int i=0;i<26;i++)
	{
		if(alpha[i]) // A~Z까지 값이 존재할 때 
		{ 
		sum += (alpha[i] * num);
		num--; 
		}
	}
	cout<<sum<<'\n';
}

<풀이 과정>

A~Z 까지 값들중 값을 0~9까지 배분할 수 있으며 알파벳의 최대 개수는 10개이고 수의 길이는 최대 8이라고 한다.

이 문제를 푸는 접근법은

TestCase:

2 

AAA => 100 * A + 10 * A + 1 * A

AAA => 100 * A + 10 * A + 1 * A

총 222A가 됨을 확인할 수 있다. 비교할 알파벳이 없기 때문에 A에 9의 값을 부여하면 되므로 999 + 999 = 1998이 된다.

2

ABBCC

DDEFF

D = 11000 * 9 (가장 큰 값)

A = 10000 * 8(다음 값)

B = 1100 * 7

E = 100 * 6

C = 11 * 5

F = 11 * 4

이런 식으로 풀어 나가면 된다. 각 자리마다 (부여한  값) * 1,10,100,1000,10000...을 곱해줘야 되기 때문에 pow함수를 활용하였고, 다 더한값을 sort함수를 통해 내림차순 정렬시켰다.

마무리 단계로 num = 9부터 시작해 벡터 alpha에 값이 존재하면 그 값에 9,8,7....을 곱해줘서 최적화된 값을 구할 수 있다.