BOJ : 1339 단어 수학

 

---

[BOJ 1339(G4) 리뷰]

쉬운듯 어려운 문제이다.

자리수가 가장 높은 알파벳에 최대한 높은 값을 주어야하는 그리디 문제이다.

 

그리디 문제이지만 이 문제는 백트래킹으로도 풀수가 있다. 알파벳의 갯수가 최대 10개 등장하니 각각의 알파벳을 9부터 0까지의 값으로 변경하여 계산하면 10!에 문제를 풀 수 있다.

 

그러나 나는 백트래킹말고 그리디+시뮬레이션으로 풀고싶었다. 그래서 일단 머리속에 떠오르는대로 구현을 하고 예제TC가 다 잘 나오길래 제출을 했더니 오답처리가 되었다. 예제에서 놓친 예외사항이 있었다.

 

처음에 구현했을땐 문자열을 입력받아 check배열을 통해 각각의 문자열의 INDEX에 자리수를 저장하고, 저장된 자리수를 우선순위큐에 담아 자리수 큰 숫자부터 높은숫자를 부여할 생각이였다. 

그러나 이렇게만 코드를 짠다면

BA

AA

같은 문제를 풀수가 없었다. A와 B의 자리수가 같으므로 먼저나온 B에 가장 높은값을 주게 되는데 그러면 98+88이 되어 올바른 정답인 89+99가 나오지 않게된다.

따라서 단순히 자리수만을 check배열에 저장하는것이 아닌, 1의 자리 10의 자리 100의 자리를 구분하여 check배열에 담고 만약 똑같은 알파벳이 또 나온다면 그 자리수에 맞는 값을 더해주면 가장 높은 자리수가 많은 순서대로 정렬을 할 수 있게된다. 위처럼 수정을하고 제출 했더니 AC가 나왔다.

 

혼자 에러를 잡아보려 하다 2시간 가량 쓴거같다. 결국 다른 블로그를 참조했지만 이렇게 여러 우선순위를 고려해야할 때 어떻게 처리해야할지 배우게 된 것같다.

 

 

---

 

#include <bits/stdc++.h>

using namespace std;
int check[26];
vector <string> ans;
int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int N;
	priority_queue <pair<int, int>, vector<pair<int,int>>, less<pair<int,int>>> pq;

	cin >> N;
	while (N--)
	{
		string word;
		cin >> word;
		ans.push_back(word);
		int len = word.size();

		//자리수 계산
		for (int i = 0; i < len; i++)
		{
			int loof = len - i;
			int digit = 1;
			for (int i = 1; i < loof; i++)
			{
				digit *= 10;
			}
			int idx = word[i] - 'A';
			if (check[idx])
			{
				check[idx] += digit;
			}
			else
			{
				check[idx] = digit;
			}
		}
	}

	//자릿수 계산해준걸 우선순위큐에 넣기
	for (int i = 0; i < 26; i++)
	{
		if (check[i])
		{
			pq.push({check[i], i});
		}
	}

	//가중치가 높은 알파벳을 9부터 내려가며 넣기
	int len = pq.size();
	for (int i = 0; i < len; i++)
	{
		auto cur = pq.top(); pq.pop();
		check[cur.second] = 9-i;
	}

	//문자열을 숫자로 바꿔 더함
	int sum = 0;
	for (int i = 0; i < ans.size(); i++)
	{
		int len = ans[i].size();
		for (int j = 0; j < len; j++)
		{
			ans[i][j] = check[ans[i][j] - 'A'] + '0';
		}
		sum += stoi(ans[i]);
	}

	cout << sum;
}