개발세발은 안되요

[백준 1339: 단어 수학] [C++] 본문

카테고리 없음

[백준 1339: 단어 수학] [C++]

금호박 2022. 9. 5. 16:05

문제 설명

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.단어 수학 문제는 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이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력:

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

코드1(실패한 코드)

#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<char> sp;
vector<int>index;
//sp에 이미 있는 알파벳인지 아닌지를 구별하기 위한 함수.
int find(vector<char> sp,char spelling,int j,int size) {
	for (int i = 0; i <sp.size(); i++) {
		if (spelling == sp[i] && index[i] >= size) return 1; //이미 vector에 있고 더 큰 수를 지정하고 있을 경우 경우, 1을 return. (변경 필요 없음)	
		else if (spelling != sp[i] && index[i] < size) return i+1;
		else if (spelling == sp[i] && index[i] < size) return -(i+1);
	}
    return -1; //만약 vector에 없은 알파벳일 경우 또는 더 큰 수를 지정 가능한 경우, -1을 return.
}
int change(vector<char> sp, char spelling) {
	int num = 9;
	for (int i = 0; i < sp.size(); i++) {
		if (spelling == sp[i]) return num; // 벡터의 가장 첫 원소일 경우 9, 두번째 원소일 경우 8,... 이렇게 return.
		num--;
	}
	return 0;
}
int main(void) {
	int N,max=0;
	int a = 0, b = 0, c = 0;
	string word[10];
	cin >> N;	//단어 개수 입력
	for (int i = 0; i < N; i++) {
		cin >> word[i];	//단어 입력
	}
	//길이 긴 순서대로 배열.
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N-1; j++) {
			if (word[j].length() < word[j + 1].length()) {
				string swap = word[j];
				word[j] = word[j + 1];
				word[j + 1] = swap;
			}
		}
	}
	//sp에 알파벳 차례대로(최댓값 나오도록) 넣기 위한 반복문
	for (int i = 0; i < N; i++) {
		int size = word[i].size();
		for (int j = 0; j < word[i].length(); j++) {
			int ans = find(sp, word[i][j],j,size);
			if (ans == -1) { // 벡터의 맨 마지막에 알파벳을 넣어주면 되는 경우
				index.push_back(size);
				sp.push_back(word[i][j]); //sp에 없는 알파벳일 경우 sp에 넣어주기.
			}
			else if(ans>=0&&ans!=1){
				ans -= 1;
				index.insert(index.begin() + ans, size);
				sp.insert(sp.begin() + ans, word[i][j]);
			}
			else if (ans < 0) {
				int ans_p = ans * (-1)-1;
				index.erase(index.begin() + ans_p);
				sp.erase(sp.begin() + ans_p);
				index.insert(index.begin() + ans_p-1, size);
				sp.insert(sp.begin() + ans_p-1, word[i][j]);
			}
			size--;
		}
	}
	for (int i = 0; i < sp.size(); i++) cout << sp[i] << " ";
	cout << endl;
	for (int i = 0; i < index.size(); i++) cout << index[i] << " ";
	cout << endl;
	for (int i = 0; i < N; i++) {
		int sum = 0;
		int size = word[i].size();
		for (int j = 0; j < word[i].size(); j++) {
			int change_num = change(sp, word[i][j]);
			switch (size)
			{
			case 8:
				sum += change_num * 10000000;
				break;
			case 7:
				sum += change_num * 1000000;
				break;
			case 6:
				sum += change_num * 100000;
				break;
			case 5:
				sum += change_num * 10000;
				break;
			case 4:
				sum += change_num * 1000;
				break;
			case 3:
				sum += change_num * 100;
				break;
			case 2:
				sum += change_num * 10;
				break;
			case 1:
				sum += change_num;
				break;
			default:
				break;
			}
			size--;
		}
		max += sum;
	}
	cout << max;
	return 0;
}

코드2(성공한 코드)

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
vector<string>word;	//입력한 단어를 넣어줄 벡터
vector<char>alpha;	//어떤 알파벳들이 입력되었는지를 저장할 벡터
vector<int>num;		//알파벳별로 1, 10, 100,, 등 몇번째 자리에 위치해있는지를 더해줄 벡터. 
					//예를 들어, AB와 BA가 입력된 경우, alpha의 A가 들어있는 index와 같은 index에 11 넣어주기.
vector<int>p_num = { 9,8,7,6,5,4,3,2,1,0 };	//num에서의 값이 큰 순서대로 9,8,7... 이렇게 곱해주기 위한 벡터.

//각 단어의 최대 자리수 계산하는 함수
int f(int size) {	
	int num = 1;
	for (int i = 1; i < size; i++) num *= 10;	//size가 4일 경우 4자리이기 때문에 num=1000 으로 출력
	return num;
}
//alpah에 이미 저장된 알파벳인지를 검사하는 함수
int find(char w) {
	for (int i = 0; i < alpha.size(); i++) {
		if (w == alpha[i]) return i;	//이미 있는 원소일 경우, 그 원소의 index를 return
	}
    return 11;	//만약 원소에 없을 경우 11 return
}
int main(void) {
	int N,max=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		string a;
		cin >> a;
		word.push_back(a);	//단어를 word 벡터에 넣어주기
	}
	for (int i = 0; i < N; i++) {
		int size = f(word[i].length());	
		for (int j = 0; j < word[i].length(); j++) {
			int ans = find(word[i][j]);
			if (ans == 11) {	//만약 아직 alpha에 넣어주지 않은 알파벳일 경우,
				alpha.push_back(word[i][j]);	//alpha에 그 알파벳을 넣어준다.
				num.push_back(size);	//num에 그 알파벳이 수의 몇번째 자리를 지정하는지를 저장해준다.
			}
			else num[ans] += size;	//만약 이미 존재하는 알파벳일 경우,기존 알파벳의 num위치에 현재 단어에서 어떤 자리를 지정하는지를 더해준다.
			size /= 10;		//자리수는 1000,100,10,1 이런 식으로 줄어들어야 한다.
		}
	}
	sort(num.begin(), num.end());	//오름차순으로 num을 정렬한다.
	for (int i = num.size() - 1,j=0; i >= 0; i--,j++) max += num[i] * p_num[j];	//num의 원소와 p_num의 원소가 거꾸로 곱해져 max에 더해진다.
	cout << max;	//최댓값 max 출력.
	return 0;
}

문제 풀이

입력받은 알파벳이 각각 0~9중 어느 수를 지정해야 최댓값이 나오는지를 구하는 문제이다. 단어의 각 알바벳이 9~0중 어떤 수를 지정하는지를 먼저 구하는 것이 아니라, 알파벳이 수의 몇번째 자리를 지정하는지의 총합를 먼저 구해야 한다. (예를 들어 100의 자리와 10의 자리를 지정할 경우, 110)

​

예를 들어, AB가 어떤 수를 나타낼지를 구하는 방법은 10*9+1*8=98 로 각 알파벳의 자리수*(9~0중 1)꼴을 구하여 더해야 한다. 이때 만약 자리수를 먼저 구하지 않고 9~0중 어느 수를 지정하는지를 먼저 구하려 한다면 코드가 복잡해질 뿐만 아니라, 올바른 최댓값이 구해지지 않는 경우가 발생할 확률이 크다.

왜냐하면 A,B,...가 무슨 수를 지정할지를 고려하는 과정에서 결국 어느 자리수에 그 알파벳이 지정되었는지를 이용할 수밖에 없는데, 이렇게 했을 경우 단순히 자리수만을 이용하기에 그 자리수가 더 낮은 알파벳이 자리수가 더 큰 알파벳보다 더 큰 수를 지정받았을 때 최댓값이 정해지는 경우를 무시하게 되기 때문이다.

(예를 들어, ABB, BB,BB,BB,BB,BB,BB,BB,BB,BB의 경우 A의 자리수가 B보다 더 크지만 실제 최댓값은 B를 9로 지정했을 때 구해진다.)

​

그리고 이런 이유로 알파벳을 자리수가 큰 순서대로 배열한 후 {9,8,7,6,5,4,3,2,1,0}순으로 지정되었을 때 최댓값일지, {8,9,7,6,5,4,3,2,1,0}순일 때 최댓값일지, 또는 다른 경우일 때 최댓값일지를 구하기는 매우 힘들다는 것이다.

결국,

1) 각 알파벳이 몇 번째 자리의 수를 지정하는지 알파벳별 그 자리수의 합을 구한다. (100,10,.. 등)

2) 구해진 자리수를 오름차순/ 또는 내림차순으로 배열한다. (나는 오름차순으로 배열했다.)

3) 구해진 가장 큰 자리수부터 9,8,...이렇게 곱하여 max에 더해준다.

4) 이렇게 구해진 max는 최댓값이다.

​

어려웠던 점, 개선점

문제 풀이에서 설명한 잘못된 풀이법이 내가 처음에 시도했던 좀 무식한 방식이다. 역시나 문제 자체를 해결하려고했다기보다는 주어진 테스트케이스를 통과하기 위해 구상한 풀이방법이었다.

(실제로 모든 테스트케이스, 검색시 나오는 반례에서는 최댓값이 정확히 출력된다.)

이런 방식으로 문제에 접근하려는 경향을 죽이도록 더 노력해야겠다.

​

그래도 공익을 위해 나의 틀린 코드를 설명하자면,

1) 각 알파벳의 자리수가 큰 순서대로 등장한 알파벳을 배열한다. 이때 알파벳별 자리수의 합을 이용

하는 것이 아닌, 단순히 단어별로 그 알파벳이 나왔을 때 조건에 따라 그 알파벳의 자리수를 업데이트

해주는 방식이 다. (더하는 것이 아닌 아예 바꾸는 것이다.)

2) 그 알파벳 배열의 원소에 각각 9,8,7...을 곱한다.

3) 2)의 결과물에 각 단어에서 그 알파벳이 등장했을 때의 자리수를 곱하여 max에 더한다.

4) max를 출력한다.

​

원본 링크 : https://blog.naver.com/ahtnwl1004/222727722807