POJ 2945 Find the Clones

제목 설명
Doubleville, a small town in Texas, was attacked by the aliens. They have abducted some of the residents and taken them to the a spaceship orbiting around earth. After some (quite unpleasant) human experiments, the aliens cloned the victims, and released multiple copies of them back in Doubleville. So now it might happen that there are 6 identical person named Hugh F. Bumblebee: the original person and its 5 copies. The Federal Bureau of Unauthorized Cloning (FBUC) charged you with the task of determining how many copies were made from each person. To help you in your task, FBUC have collected a DNA sample from each person. All copies of the same person have the same DNA sequence, and different people have different sequences (we know that there are no identical twins in the town, this is not an issue).
상기 설명 정보에 따라 본 문제를 추상적으로 다음과 같이 할 수 있다. 문자열을 주면 수량은 n이고 모든 문자열의 길이는 m이며 출력은 i(1<=i<=n)회의 문자열의 개수를 나타낸다.
문제 해결 방법:
최근에 사전나무를 공부하고 있는데 처음에는 이 문제를 보고도 사전나무로 하려고 했어요.생각해 보니 사실은 더 간단한 맵으로 실현할 수 있다.맵의 변수로 형식을 정의하고 문자열이 나타나는 횟수를 기록합니다.그리고 수조num[20000]을 열어 i(1<=i<=n) 차례의 문자열의 개수를 기록합니다.맵을 반복하여 현재 문자열에 나타난 글자 수를 k 로 줄이고 num[k]를 업데이트하여num[k]++로 만듭니다.
실현 시 주의해야 할 점:
1. 맵을 정의할 때 키 형식이char*이기 때문에 사용자 정의 비교 함수가 필요합니다.
2. 매번 new의 새로운 문자열을 피하기 위해 문자 그룹을 정의합니다. new가 필요한 곳은 직접 그룹에서 가져옵니다.
Memory: 1184K Time: 2938MS

#include <cstdio>
#include <map>
#include <cstring>
using namespace std;

struct cmp // 
{
	bool operator()(const char *s1, const char *s2) const
	{
		return strcmp(s1, s2) < 0;
	}
};

int main()
{
	char *dna;
	char dnas[20000][21]; // ， new 
	int num[20000];
	map<char*, int, cmp> mp;
	int i, j, m, n;
	
	while(scanf("%d%d", &n, &m))
	{
		if(n == 0 && m == 0)
			break;

		j = 0;
		mp.clear();
		for(i = 0; i < n; i++)
		{
			dna = dnas[j++]; // 
			scanf("%s", dna);
			mp[dna]++;
		}

		memset(num, 0, sizeof(num));
		map<char*, int, cmp>::iterator iter = mp.begin();
		while(iter != mp.end())
		{
			num[iter->second - 1]++;
			iter++;
		}
		for(i = 0; i < n; i++)
		{
			printf("%d
", num[i]);
		}
	}

	return 0;
}

맵을 이용하여 실현하면 프로그램의 실행 효율이 비교적 낮다.시간이 있으면 다시 Trie 방법으로 실현하고 양자의 효율을 비교한다.