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

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

1339번: 단어 수학

걸린 시간 : 17분 46초

---

아이디어

1. 입력을 받으면서 알파벳들의 가중치를 설정해준다. ABC 가 들어오면 A의 가중치에 100, B의 가중치에 10, C의 가중치에 1을 추가해주는 식이다.
2. 입력이 끝나면 가중치가 큰 알파벳 순으로 9부터 내려가면서 할당한다.

끝이다.... 어렵지는 않은 문제

Map을 Value 기준으로 정렬

 

여기서 가중치를 map으로 구현하는데, map은 key를 기준으로 정렬할 수 있다. 하지만 이 문제와 같이 value로 정렬해야 할 수 있다. C++에서는 이를 바로 정렬할 수는 없고, vector로 옮겨서 정렬하는 식으로 구현해야 한다. 코드는 다음과 같다.

vector<pair<char, int> > v(m.begin(), m.end());
sort(v.begin(), v.end(), cmp);

맵의 요소를 pair로 바꿔 그대로 vector에 복사한다. 이것을 cmp 함수를 기준으로 정렬한다. value는 second 값이므로 value를 기준으로 내림차순 정렬하고 싶으면 다음과 같은 cmp함수를 구현한다.

bool cmp(const pair<char, int>& a, const pair<char, int>& b) {
	return a.second > b.second;
}

정답 코드

#include <bits/stdc++.h>
using namespace std;
 
map<char, int> weight;
int N, ans, val = 9;
 
bool cmp(const pair<char, int>& a, const pair<char, int>& b) {
	return a.second > b.second;
}
 
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		string word;
		cin >> word;
		for (int j = 0; j < word.size(); j++) {
			weight[word[j]] += pow(10, word.size()-j-1);
		}
	}
	vector<pair<char, int> > v(weight.begin(), weight.end());
	sort(v.begin(), v.end(), cmp);
	for (auto p : v) {
		ans += p.second * val;
		val--;
	}
	cout << ans;
	return 0;
}