POJ 2945 Find the Clones

2314 단어 iteratoreach
제목 설명
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 방법으로 실현하고 양자의 효율을 비교한다.
POJ_2236(병렬 검색 집합)
E - Maximum Square

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage