[baekjoon 1339] 단어 수학 (브루트포스, 그리디) (C++)

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

1339번: 단어 수학

알파벳 대문자로 이루어진 단어에 0~9까지 숫자를 대입해서 그 결과가 가장 큰 숫자를 찾는 문제이다.

예를 들어 ABC + AAA이면 A에 9, B에 8, C에 7을 대입하면 987+999 = 1986이 결과가 되는 것이다.

 

즉, 알파벳 대문자가 나온 빈도수와 자릿수에 맞춰서 가장 큰 9부터 가장 작은 0을 어떻게 대입해야 할지를 정해줘야 한다.

 

방법으로는

1. 완전 탐색으로 모든 조합으로 매번 대입해서 그중 가장 최댓값을 구하는 것이다.

모든 단어에 포함된 알파벳의 최대 개수는 10개이고, 수의 길이는 8이 최대이므로 충분히 완전 탐색이 가능하다.

ABC + AAA이면 총 알파벳이 3개이므로 9, 8, 7부터 ABC순으로 789, 798, 879, 897, 987, 978을 각각 맞춰보고 987 때 최대가 되고, 그 값을 출력하면 될 것이다.

 

2. 그리디 하게 푸는 방법으로 주어진 단어 두 개를 돌면서 자릿수를 저장해 두고, 그리디 하게 가장 큰 값부터 9,8,7.. 을 주는 것이다.

ABC의 경우 A는 100, B는 10, C는 1 + AAA는 A가 111 모두 가져간다.

그러면 A에는 총 211이 저장, B에는 10, C에는 1이 저장되고 A에 9, B에 8, C에 7을 주면

211*9 + 10*8 + 1*7로 1899 + 80 + 7 = 1986이 나오게 된다.

 

내 풀이는 그리디 한 방법이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

int N;
string s;
vector<string> stringList;
int answer = 0;
int alphabet[26];
vector<int> v;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s;
		stringList.push_back(s);
	}

	for (int i = 0; i < stringList.size(); i++) {
		reverse(stringList[i].begin(), stringList[i].end());
		for (int j = 0; j < stringList[i].size(); j++) {
			char character = stringList[i][j];
			alphabet[character - 'A'] += pow(10, j);
		}
	}

	for (int i = 0; i < 26; i++) {
		if (alphabet[i] != 0)
			v.push_back(alphabet[i]);
	}

	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());

	for (int i = 0, k = 9; i < v.size(); i++, k--) {
		answer += v[i] * k;
	}
	cout << answer;
}

완전 탐색과 그리디에 약한 나에게 좋은 문제였다.