[BOJ 백준] 단어 수학(1339) C++

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

1339번: 단어 수학

 

문제 설명 : 

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

 

출력 : 

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

 

예제 입력 : 

2
GCF
ACDEB

 

예제 출력 : 

99437

 

접근법 : 

1) 어떻게 풀 것인가?

 

N진법의 덧셈의 최댓값은 어떻게 구해지는가에 대한 고민

 

 

 

2) 시간복잡도

 

3) 공간복잡도

 

4) 풀면서 놓쳤던점

 

5) 이 문제를 통해 얻어갈 것

 

 

C++ 코드 : 

// 1339 단어수학 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int N;
int ans;						// ans : 정답

int alphabet[26];

bool descSort(int a, int b) {
	if (a > b) return true;
	return false;
}

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	char input[9];
	int length;
	for (int i = 1; i <= N; i++) {
		scanf("%s", input);

		// ** 입력받은 수를 파싱해서 더한다
		// ex> ABC 의 경우 A = 100 / B = 10 / C = 1 로 파싱해서 넣기
		length = strlen(input);

		int mul = 1;
		for (int j = length - 1; j >= 0; j--) {
			alphabet[input[j] - 'A'] += mul;
			mul *= 10;
		}
	}

	// 2. 정렬한다.
	sort(alphabet, alphabet + 26, descSort);

	// 3. 정답을 구한다
	for (int i = 0; i < 10; i++) {
		ans += alphabet[i] * (9 - i);
	}
	printf("%d", ans);

	return 0;
}

#endif