백준 1339번(그리디)

백준 1339번(그리디)

정말 오랜 시간을 투자하였고, 정말 어렵게 풀었습니다. 이렇게 어렵게 해결해야할 문제였나 싶을 정도로 어렵게 풀었습니다. 삽질을 많이 하다보니 코드가 점점 복잡해져서 그렇게 된 것 같기도 합니다. 처음 아이디어는 vector배열을 이용해서 각 알파벳 문자열을 자릿수에 맞게 저장한뒤 자릿수가 높은 것부터 maxNum를 배정해주고 maxNum을 낮추고 하는 과정을 반복하는 것이었습니다. 하지만 정답이 아니었습니다. 잘 생각해보면 예외가 존재할 수 있는 방법이었습니다. 이 문제는 방정식으로 생각하면 해결할 수 있었습니다. 예를 들어 'ABC'는 '100A+10B+C'라고 생각하는 것입니다. 이렇게 함으로써 앞에 계수 기준으로 내림차순으로 나열한 뒤 차례대로 maxNum을 배정하고 maxNum값을 낮추고 하는 것을 반복하는 방식으로 해결할 수 있었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> // pow를 사용하기위해

using namespace std;

bool compare(pair<char, int> a, pair<char, int> b) { // second, 즉 계수 기준으로 내림차순 정렬
	return b.second < a.second;
} 

int main() {
	string str;
	int n;
	int num = 0;
	int idx = 0;
	int maxNum = 9;
	int result = 0;
	vector<char> v[8]; // 각 자릿수에 맞게 알파벳 저장
	vector<pair<char, int>> alph; // 알파벳과 해당 계수
	char exist[10]; // 현재 알파벳이 이미 값이 배정됬는지 확인

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> str;
		for (int j = str.size(); j > 0; j--) {
			v[8 - j].push_back(str[str.size() - j]);
		}
	}

	int existIdx = 0;

	for (int i = 0; i < 8; i++) {
		for (auto& element : v[i]) {
			if (count(exist, exist + 10, element) == 0) {
				alph.push_back(pair<char, int>(element, pow(10, 7 - i)));
				exist[existIdx] = element;
				existIdx++;
			}
			else {
				idx = 0;
				for (auto& a : alph) {
					if (a.first == element) {
						a.second += pow(10, 7 - i);
					}
					idx++;
				}
			}
		}
	}

	sort(alph.begin(), alph.end(), compare);

	for (auto& element : alph) {
		result += maxNum * element.second;
		if (maxNum == 0) {
			continue;
		}
		maxNum--;
	}

	cout << result;

	return 0;
}