[순열] 단어수학 (boj.kr/1339)

단어수학 (boj.kr/1339)

풀이코드( 순수 재귀로만 해보려다가 스파게티 코드를 만들었다. )

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
#include <string>
using namespace std;
// 1339 단어 수학

int n;

string words[10];
string alphabets;
int alphaNum[10] = {-1};
bool isUsed[10] = {false};
int ans = -123456789;

int getSum(){
	int sum = 0;
	for(string word : words){
		for(int i = 0; i < word.size(); i++){
			sum += alphaNum[alphabets.find(word[i])];
		}
	}
	return sum;
}

void solve(int index){
	// 기저 사례 : 
	if(index == alphabets.size()){
		int max = getSum();
		ans = ans > max ? ans : max;
	}
	
	for(int i = 9; i > 0; i--){
		// 사용한 수라면 생략
		if(!isUsed[i]) continue;
		
		else{
			isUsed[i] = true;
			alphaNum[index] = i;
			solve(index + 1);
			isUsed[i] = false;
			alphaNum[index] = -1;
		}
	}
	
}

int main(){
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> words[i];
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < words[i].size(); j++){
			// 이미 넣은 알파벳이 아니라면
			if(!alphabets.find(words[i][j])){
				alphabets.push_back(words[i][j]);
			}
		}
	}
	sort(alphabets.begin(), alphabets.end());
	
	fill_n(alphaNum, 10, -1);
	fill_n(isUsed, 10, false)
	
	solve(0);
	
	printf("%d", ans);
	
}

풀이코드 ( 순열 next_permutation 활용 )

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
#include <string>
using namespace std;
// 1339 단어 수학

int n;

string words[10];
string alphabets;

// find 로 인해 시간초과
int getSum(vector<int>& num){
	int sum = 0;

	for(string word : words){
		for(int i = 0; i < word.size(); i++){
			sum += pow(10, (word.size() - 1) - i) * num[alphabets.find(word[i])];
		}
	}

	return sum;
}

char alpha[256];

// 강의 버전
int calc(vector<int>& num){
	int m = alphabets.size();
	int sum = 0;
	for(int i = 0; i < m; i++){
		alpha[alphabets[i]] = num[i];
	}
	
	for(string word : words){
		int tmp = 0;
		for(int i = 0; i < word.size(); i++){
			// 시간 초과
			// sum += pow(10, ((word.size() - 1) - i)) * alpha[word[i]];
			tmp = tmp * 10 + alpha[word[i]];
		}
		sum += tmp;
	}
	
	return sum;
}

int main(){
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> words[i];
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < words[i].size(); j++){
				alphabets.push_back(words[i][j]);
		}
	}
	
	sort(alphabets.begin(), alphabets.end());
	alphabets.erase(unique(alphabets.begin(), alphabets.end()), alphabets.end());
	
	int m = alphabets.size();
	
	vector<int> num;
		
	for(int i = 9; i > 9 - m; i--){
		num.push_back(i);
	}
	
	// num 자체도 정렬 해주어야 함. 해주지 않으면 98765 이런식으로 되어있어서, 모든 next_permutation 을 돌지 못함. 하지만, 정렬해주어, 56789 부터 시작한다면 모든 next_permutation 가능하다.
	sort(num.begin(), num.end());
	
	int ans = -123456789;
	
	do {
		int sum = calc(num);
		if(ans < sum){
			ans = sum;
		}
	}while(next_permutation(num.begin(), num.end()));
	cout << ans << endl;
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

1. 0부터 9까지의 수. 서로 다른 알파벳의 개수가 10개.

- 그러므로, 최대 경우는 10! 이다. 브루트 포스로 가능하겠다.

2. 합의 최대를 구하는 것이기에 무조건 숫자는 큰 것일수록 좋다.

- 서로 다른 알파벳이 M 개 라면, 9 부터 아래로, 차례대로 M 개만 넣어서 하면 된다.

3. 예제를 살펴보자.

GCF

ACDEB

총 알파벳은 {A, B, C, D, E, F, G} 7개이다.

그렇다면, {9, 8, 7, 6, 5, 4, 3} 7 개의 수만을 보면 된다.

7개의 알파벳에 7개의 숫자를 매칭시키는 것. 바로 순열을 이용할 수 있다.

{A, B, C, D, E, F, G} 가 있다면,

{9, 8, 7, 6, 5, 4, 3,} 일 때의 합

{9, 7, 8, 6, 5, 4, 3} 일 떄의 합.. 

다음 순열을 찾아나가며 max 값만을 취하면 된다.

풀이

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

배운 것이 많은 풀이이다.

1. pow 연산 자체가 시간 초과를 일으키는 원인이 될 수 있다.

- pow 자체도 시간 복잡도가 O(1) 이 아니기에 시간을 지연시킨다. pow 연산 대신에 기존의 tmp 값을 10 곱하고 거기에 추가적인 값을 더해주는 방식을 사용했는데, 이 연산은 O(1) 이기에, 답이 통과되었다.

2. string 의 find 연산 대신 사용한 테크닉

- alpha char 배열을 이용한 코드를 잘 생각해보자.

3. unique 의 사용.

- STL 에서 쓸모있는 함수는 끝이 없구나라는 생각이 든다.

4. 가장 중요했던 순열의 사용.

- 문제의 핵심적인 부분에서 어떤 접근 방식을 사용할지를 결정하는 것이 풀이를 좌지우지 한다. 여러 유형을 익혀서, 문제를 이해해나가다가 어떤 유형인지 알 수 있을 정도가 되어야 겠다.