[백준] 1339번 - 단어 수학

링크

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

1339번: 단어 수학

풀이

여러 단어가 주어졌을때 단어를 숫자로 변환한 값의 최대 합을 구하는 문제이다.

 

문제를 풀기전에 생각 해봐야 할것은

1. 알파벳이 어느 위치에 있는지

2. 알파벳이 얼마나 나오는지

 

위의 두가지를 이용하면 문제를 풀 수 있다.

 

2번째 예시를 예로 들어보겠습니다.

 

알파벳의 위치에 따라 체크를 해주게 되면 밑의 표 처럼 되고

 

알파벳이 얼마나 나오는지 값에 따른 정렬을 하여 9부터 0까지 곱해주어 더해주면 밑의 표처럼 나오게 됩니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>

#define SIZE 1010

using namespace std;

typedef long long int ll;

const int INF = 2000000000;

map<char, int> _map;
priority_queue<int> pq;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N; cin >> N;

	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		int zari = 1;
		
		for (auto it = s.rbegin(); it != s.rend(); it++) {
			if (_map.find(*it) == _map.end())
				_map[*it] = zari;
			else
				_map[*it] += zari;
			zari *= 10;
		}
	}

	for (auto it = _map.begin(); it != _map.end(); it++) {
		pq.push(it->second);
	}

	int num = 9, sum = 0;
	while (!pq.empty()) {
		sum += pq.top() * num--;
		pq.pop();
	}

	cout << sum;
	
}