[c++] 백준 - 단어수학

1. 문제

2. 입출력

3. 문제 해설

 

처음엔 완전 해맸다. 

처음엔 단어의 개수가 N(1<= N <= 10)개 이므로 vector <char> v[11]을 만들어 최대 길이 부터 하나씩 제거해가야하나... 라는 생각으로 stack에 queue에 많은 자료구조들을 적용시켜 보았다. 하지만 골드 4의 난이도에 비해 신경쓸 점이 너무 많았고 이렇게 푸는 거 말고 좀 더 쉬운 방법이 있을 수 있다는 생각이 들어 다시 키보드에서 손을 때고 이면지에 끄적이기 시작했다. 

 

우선 이 문제는 자리수가 굉장히 중요한 문제였다. 자리수가 높으면 높을수록 높은 숫자를 가져가기 때문이다. 

 

예제와 같이 

GCF

ACDEB가 있을 때

 

A가 가장 높은 자리 이므로 9 

C는 그 다음 높은 자리 이므로 8

G와 D는 각각 1번씩 나오고 그 다음 높은 자리이므로 둘 중에 하나는 7 하나는 6이 된다. 

 

이런 식으로 정렬을 해줘야한다. 

 

그런데 여기서 문제는 하나의 문자가 2번 이상 나올 때였다. 

2번 이상 나온다면 같은 자리 수에 해당하는 문자라도 빈도 수에 따라 배당되는 숫자가 달라지기 때문이다. 

따라서 나는 

struct alpha {
    int idx;
    int val;
}

위와 같은 구조체를 하나 만들어 뒤에서 부터 10을 곱한 값을 val에 더해주었다. 

 

예를 들면 

GCF라면

F는 1 

C는 10

G는 100

 

ACDEB라면

B = 1;

E = 10;

D = 100;

C = 아까 위에 10이 이미 더해진 상태이므로 10 + 1000 = 1010

A = 10000

 

위처럼 값을 넣으면 alphabet배열이 다음과 같이 된다. 

 

	A	B	C	D	E	F	G
idx	1	2	3	4	5	6	7
val	10000	1	1010	100	10	1	100

그 후 custom compare함수를 작성해 위의 배열을 정렬해주었다. 

	A	C	D	G	E	B	F
idx	1	3	4	7	5	2	6
val	10000	1010	100	100	10	1	1

위와 같이 정렬된 배열을 차례대로 

int num = 9;
int ans = 0;
for(int i=0; i < 26; i++) {
	if(alphabet[i].idx == 0) break;
    ans += alphabet[i].val * num;
    num --;
}

다음과 같이 작성해주면 최종 결과가 나온다. 

 

#pragma warning (disable : 4996)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct alpha {
	int idx;
	int val;
};
int N; // 단어의 개수
alpha alphabet[26];
int ans;
bool cmp(alpha a, alpha b) {
	if (a.val > b.val) return true;
	else return false;
}
void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string temp;
		cin >> temp;
		int idx = 1;
		for (int i = temp.size()-1; i >= 0; i--) {
			alphabet[temp[i] - 'A'].val += idx;
			alphabet[temp[i] - 'A'].idx = temp[i] - 'A'+1;
			idx *= 10;
		}
	}
}

void sol() {
	sort(alphabet, alphabet + 26, cmp);
	int num = 9;
	for (int i = 0; i < 26; i++) {
		if (alphabet[i].idx == 0) break;
		ans += (num * alphabet[i].val);
		num--;
	}
}
int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	input();
	sol();
	cout << ans << "\n";
	return 0;
}