한 수조에서 수는 모두 두 냥으로 나타나지만 세 개의 수가 유일하게 나타나 이 세 개의 수를 찾아낸다.

이 문제는 Trie 색인 트리를 사용했는데 맞는지 모르겠지만 프로그램이 실행된 후에 결과가 맞았습니다. 먼저 프로그램을 붙여서 같이 연구했습니다.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define branch_num 10
typedef struct trie_node
{
	int count;
    struct trie_node *child[branch_num];
}TrieNode,*TrieTree;
TrieNode *trie_create_node()
{
	TrieNode *temp=(TrieNode*)malloc(sizeof(TrieNode));
	temp->count=0;
	memset(temp->child,0,sizeof(temp->child));
	return temp;
}
void trie_insert_node(TrieTree t,int n)
{
	TrieNode *location=t;
	char *p=(char*)malloc(sizeof(char)*10);
	sprintf(p,"%d",n);
	while(*p!='\0')
	{
		if(location->child[*p-'0']==NULL)
		location->child[*p-'0']=trie_create_node();
		location=location->child[*p-'0'];
		p++;
	}
	location->count+=1;
}
int trie_count_word(TrieTree t,int n)
{
	TrieNode *location=t;
	char *p=(char*)malloc(sizeof(char)*10);
	sprintf(p,"%d",n);
	while(*p!='\0'&&location!=NULL)
	{
		location=location->child[*p-'0'];
		p++;
	}
	return location->count;
}
void main()
{
	int num[]={23,43,45,67,12,98,23,43,45,67,12,98,2,5,6};
	TrieTree t=trie_create_node();
	int len=sizeof(num)/sizeof(int);
	int i;
	for(i=0;i<len;i++)
		trie_insert_node(t,num[i]);
	for(i=0;i<len;i++)
		if(trie_count_word(t,num[i])==1)
			printf("%d\t",num[i]);
	printf("
"); }

좋은 웹페이지 즐겨찾기