#1339 단어 수학

# 문제

# 입력 및 출력

# 풀이

처음에 생각한 풀이는

길이가 긴 순서대로 정렬하고 앞에서부터 한자리씩 자르면서 계속 길이순으로 정렬한다음

순서대로 9, 8, 7... 이런식으로 값을 부여하려고 했다

// 틀린 풀이
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<string> word;
vector<string> c;
map<char, int> m;

bool compare(string a, string b) { // 정렬 함수
	return a.length() > b.length();
}

int main() {
	int n, num = 9, sum = 0;
	cin >> n;
	string t;
	for (int i = 0; i < n; i++) { // 입력 받음
		cin >> t;
		word.push_back(t);
		c.push_back(t);
	}
	while (!c.empty()) {
		sort(c.begin(), c.end(), compare); // 길이가 긴 순서대로 정렬
		if (m.find(c.front()[0]) == m.end()) { // map에 존재하지 않는 key값은 map에 삽입
			m[c.front()[0]] = num; // 9부터 내림차순으로 값 부여
			num--;
		}
		c.front() = c.front().substr(1, c.front().length()); // 앞자리 자름
		if (c.front() == "") c.erase(c.begin()); // 문자열 자르고 나서 빈 문자열이 되면 벡터에서 삭제
	}
	for (int i = 0; i < n; i++) {
		string tmp = "";
		for (int j = 0; j < word[i].length(); j++) {
			tmp += to_string(m[word[i][j]]); // map에서 값 가져와서 알파벳을 숫자로 변경
		}
		sum += stoi(tmp); // 계산
	}
	cout << sum;
}

입력 예제 2번을 대입해보면

ACDEB

GCF 이 순서대로 정렬되고

map에 A=9 넣고 A자르면 CDEB, GCF가 남고 이걸 다시 길이순으로 정렬

벡터가 빌때까지 반복

 

좀 복잡한 것 같아서 벡터 대신 정적 배열을 사용

// 틀린 풀이
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
string word[10];
string c[10];
map<char, int> m;

bool compare(string a, string b) {
	return a.length() > b.length();
}

int main() {
	int n, num = 9, sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> word[i];
		c[i] = word[i];
	}
	sort(c, c + n, compare);
	while (c[0]!="") {
		if (m.find(c[0][0]) == m.end()) {
			m[c[0][0]] = num;
			num--;
		}
		c[0] = c[0].substr(1, c[0].length());
		sort(c, c + n, compare);
	}
	for (int i = 0; i < n; i++) {
		string tmp = "";
		for (int j = 0; j < word[i].length(); j++) {
			tmp += to_string(m[word[i][j]]);
		}
		sum += stoi(tmp);
	}
	cout << sum;
}

위의 코드와 알고리즘은 동일하지만 배열로 변경해서 코드가 복잡해보이는 부분을 좀 줄여봄,,ㅋㅋ

 

근데 이렇게 푸니까 예제는 전부 돌아가지만 문제가 생김

예) 2 AB BB 이렇게 들어가면 정렬했을 때 두 문자열의 길이가 동일하기 때문에 AB BB로 정렬된 상태다

이렇게 되면 B가 가장 큰 값이 들어가야하는데 A에 가장 큰 9가 들어가서 올바른 답이 안나오게 됨

-> 가장 많이 나오는 알파벳 기준으로도 정렬해줘야함

// 틀린 풀이
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
string word[10];
string c[10];
map<char, int> cnt;
map<char, int> m;

bool compare(string a, string b) { // 정렬 함수를 수정해줌
	int i = 0;
	if(a.length()!=b.length()) return a.length() > b.length();
	else {
		while (cnt[a[i]] == cnt[b[i]] && i < a.length()) i++;
		return cnt[a[i]] > cnt[b[i]];
	}
}

int main() {
	int n, num = 9, sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> word[i];
		c[i] = word[i];
		for (int j = 0; j < word[i].length(); j++) {
			cnt[word[i][j]]++;
		}
	}
	sort(c, c + n, compare);
	while (c[0]!="") {
		if (m.find(c[0][0]) == m.end()) {
			m[c[0][0]] = num;
			num--;
		}
		c[0] = c[0].substr(1, c[0].length());
		sort(c, c + n, compare);
	}
	for (int i = 0; i < n; i++) {
		string tmp = "";
		for (int j = 0; j < word[i].length(); j++) {
			tmp += to_string(m[word[i][j]]);
		}
		sum += stoi(tmp);
	}
	cout << sum;
}

그래서 정렬함수에서 길이가 같을 때 가장 많이 나온 알파벳을 기준으로 정렬해줬음

 

하지만 이 방법도 틀렸다고 나옴,,ㅋㅋㅋ

 

그래서 결국 구글링을 해봤다,,

https://excited-hyun.tistory.com/145

[백준 1339 - C++] 단어 수학 : 브루트포스

알고리즘은 위 블로그 참고

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int alpha[26];

int main() {
	int n, sum = 0, num = 9;
	cin >> n;
	string str;
	for (int i = 0; i < n; i++) {
		cin >> str;
		int digit = 1;
		for (int j = str.length() - 1; j >= 0; j--) { 
            // 입력받은 문자열의 가장 뒤부터 계산함 (1, 10, 100 순으로 늘려나가기 위해)
			alpha[str[j]-'A'] += digit; 
			digit *= 10;
		}
	}
	sort(alpha, alpha + 26, greater<int>()); // 내림차순 정렬
    // n은 최대 10, 최소 1개기 때문에 가장 많은 경우에도 9개의 숫자만 있으면 됨 
	for (int i = 0; i < 26; i++) { 
    	// 따라서 10개가 넘어가면 어처피 alpha값은 다 0이기 때문에 num이 마이너스가 되어도 상관이 없음
	// 결론은 num이 9에서 26번 --되어도 결과값엔 문제가 없음
        sum += alpha[i] * num; 
		num--; 
	}
	cout << sum;
}

문제 적힌 대로 코드를 짜려고 하기 보다는 알고리즘을 생각하는 방향으로 짜보자,,ㅠㅠ

자꾸 글 그대로 코드를 정직하게 짜려고 하니까 복잡해지는 것이다,,,,ㅋ

DFS로 푸는 방법도 있던데 다음에 풀어보기,,! 북마크 해둠

https://imnotabear.tistory.com/85

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