[백준]1032번 합 - C/C++

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

1132번: 합

문제

N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 시작하는 수는 없다. 이때, 가능한 수의 합 중 최댓값을 구해보자.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 수가 주어진다. 수의 길이는 최대 12이다. 적어도 한 알파벳은 수의 가장 처음에 주어지지 않는다.

출력

첫째 줄에 합의 최댓값을 출력한다.

---

 

ABC, BCA가 들어온다면 이 숫자들의 합은 

   A * 101

+ B * 110

+ C * 11 이 된다. 그런 다음 곱하는 수가 가장 큰 순서 ( B - C - A)의 순서로 9,8,7... 숫자를 배정해야한다.

    이러한 방식으로 곱하는 수를 기준으로 내림차순으로 문자들을 정렬한다. 이 때 숫자 0까지 배정을 해야하는 경우 첫째 자리에 온 수 (0이 될 수 없는 문자)를 저장해두었다가 곱하는 수가 가장 작은 문자가 0 이 될 수 없는 경우 그 다음 곱하는 수가 작은 문자를 확인해가며 0이 될수 있는 문자를 정한다. 그 문자를 정렬된 배열에서 맨 뒤로 보내고 (0으로 지정) 나머지 문자들의 순서를 한칸씩 당겨주면 된다. 

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

pair <long long, char> arr[12];
bool flag[12] = { 0 };
long long num[12] = { 0 };
int n,number;
long long ans;
string s;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	for (int i = 0; i < 10; i++) {
		arr[i].first = 0;
		arr[i].second = 'A' + i;
	}

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		long long times=1;
		for (int k = s.length()-1 ; k >=0; k--) {
			arr[s[k]-'A'].first += times;
			times *= 10;
		}
		flag[s[0] - 'A'] = true;
	}

	sort(arr, arr + 10, greater<>());
	number = 9;	

	for (int i = 0; i < 10; i++) {
		if (arr[i].first == 0) break;
		if (i == 9 && flag[arr[9].second - 'A']) {			
			for (int k = 8; k >= 0; k--) {
				if (!flag[arr[k].second - 'A']) {
					char temp = arr[k].second;
					double tempd = arr[k].first;
					for (int j = k; j < 9; j++) {
						arr[j].first = arr[j + 1].first;
						arr[j].second = arr[j + 1].second;
					}
					arr[9].second = temp;
					arr[9].first = tempd;
					break;
				}
			}
		}
	}
	for (int i = 0; i < 10; i++) {
		if (arr[i].first) {
			num[arr[i].second - 'A'] = number--;
		}
		else {
			break;
		}
	}

	for (int i = 0; i < 10; i++) {
		ans += num[arr[i].second - 'A'] * arr[i].first;
	}

	cout << ans;
}

---

     숫자가 12자리까지 가능하여 double을 사용했는데 중간에 times 를 int 로 설정하여 오류가 났다. 하지만 나름 빠르게 발견하여 원활히 문제를 풀 수가 있었다!