글 읽기 - 틀린 이유를 모르겠습니다.

lkgsns 3년 전 0

해쉬를 이용해서 풀어봤구요, 제가 생각할 수 있는 범위내에서 모든 예제를 돌려봤습니다.

맞게 나오는거 같은데 왜 틀린지 모르겠습니다. 부탁드립니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MOD 1000003

typedef struct s_node
{
	char			*key;
	struct s_node	*next;
}				t_node;

typedef struct s_map
{
	int	 size;
	t_node		**map;
}				t_map;

t_node	*create_elem(char *name)
{
	t_node	*new;

	if (!(new = malloc(sizeof(t_node))))
		return (0);
	new->key = strdup(name);
	new->next = 0;
	return (new);
}

t_map	*map_init(void)
{
	t_map *map;

	if (!(map = malloc(sizeof(t_map))))
		return (0);
	map->size = 0;
	if (!(map->map = malloc(sizeof(t_node) * MOD)))
	{
		free(map);
		return (0);
	}
	for (int i = 0; i < MOD; i++)
		map->map[i] = 0;
	return (map);
}

long long get_hash(char *key)
{
	long long hash = 0, power = 1;
	int i, len;

	i = 0;
	len = strlen(key);
	while (i < len)
	{
		hash = (hash + power * (key[i] - 'A' + 1)) % MOD;
		power = power * 31 % MOD;
		i++;
	}
	return (hash);
}

int str_cmp(const void *a, const void *b)
{
	return (strcmp(*(char **)b, *(char **)a));
}

int main(void)
{
	int 		N, i, j;
	char 		name[6], cases[6];
	long long	 hash;
	t_map		 *map;

	scanf("%d", &N);
	map = map_init();
	while (N--)
	{
		scanf("%s %s", name, cases);
		hash = get_hash(name);
		if (strcmp(cases, "enter") == 0)
		{
			if (!map->map[hash])
			{
				map->map[hash] = create_elem(name);
				map->size++;
			}
		}
		else if (strcmp(cases, "leave") == 0)
		{
			if (map->map[hash])
			{
				map->map[hash] = 0;
				map->size--;
			}
		}
	}

	if (map->size <= 0)
		return (0);

	char **result;
	result = malloc(sizeof(char *) * map->size);
	for (i = 0; i < map->size; i++)
		result[i] = malloc(sizeof(char) * 6);
	j = 0;
	for (i = 0; i < MOD; i++)
	{
		if (map->map[i] != 0)
		{
			result[j] = map->map[i]->key;
			j++;
		}
	}

	qsort(result, map->size, sizeof(result[0]), str_cmp);

	for (i = 0; i < map->size; i++)
		printf("%s\n", result[i]);
	return (0);
}

djm03178 3년 전 1

해시의 충돌에 대해서 아시나요?

최대 100만개의 문자열에 대한 해시를 저장해야 하는데 1000003 크기의 해시를 사용하면 충돌이 거의 100%에 가까운 확률로 발생한다고 할 수 있습니다.

djm03178 3년 전 1

그를 위해서 next를 만들어두신 것 같은데 실제로 사용을 하지 않고 중복되는 경우 그대로 무시하고 있습니다.

lkgsns 3년 전 0

말씀하신대로 충돌을 고려하여 리스트를 이용하여 체이닝을 해주었습니다... 근데 또 틀렸네요 ㅜ 여러가지 시도를 해봤지만 잘 모르겠습니다. 또 무슨 문제가 있을까요?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MOD 10000007

typedef struct s_node
{
	char			*key;
	struct s_node	*next;
}				t_node;

typedef struct s_map
{
	int	 size;
	t_node		**map;
}				t_map;

t_node	*create_elem(char *name)
{
	t_node	*new;

	if (!(new = malloc(sizeof(t_node))))
		return (0);
	new->key = strdup(name);
	new->next = 0;
	return (new);
}

t_map	*map_init(void)
{
	t_map *map;

	if (!(map = malloc(sizeof(t_map))))
		return (0);
	map->size = 0;
	if (!(map->map = malloc(sizeof(t_node) * MOD)))
	{
		free(map);
		return (0);
	}
	for (int i = 0; i < MOD; i++)
		map->map[i] = 0;
	return (map);
}

long long get_hash(char *key)
{
	long long hash = 0, power = 1;
	int i, len;

	i = 0;
	len = strlen(key);
	while (i < len)
	{
		hash = (hash + power * (key[i] - 'A' + 1)) % MOD;
		power = power * 31 % MOD;
		i++;
	}
	return (hash);
}

int str_cmp(const void *a, const void *b)
{
	return (strcmp(*(char **)b, *(char **)a));
}

int map_insert(t_map *map, char *key)
{
	t_node *curr;
	long long hash;

	hash = get_hash(key);
	if (!map->map[hash])
	{
		map->map[hash] = create_elem(key);
		map->size++;
		return (1);
	}
	curr = map->map[hash];
	while (curr)
	{
		if (strcmp(key, curr->key) == 0)
			return (0);
		curr = curr->next;
	}
	curr = create_elem(key);
	map->size++;
	return (1);
}

int map_delete(t_map *map, char *key)
{
	t_node 	*curr;
	t_node 	*prev;
	long long 	hash;

	hash = get_hash(key);
	curr = map->map[hash];
	prev = 0;
	while (curr)
	{
		if (strcmp(key, curr->key) == 0)
			break;
		prev = curr;
		curr = curr->next;
	}
	if (!curr)
		return (0);
	if (prev)
		prev->next = curr->next;
	else
		map->map[hash] = curr->next;
	free(curr);
	map->size--;
	return (1);
}

int main(void)
{
	int 		N, i, j;
	char 		name[6], cases[6];
	long long	 hash;
	t_map		 *map;

	scanf("%d", &N);
	map = map_init();
	while (N--)
	{
		scanf("%s %s", name, cases);
		hash = get_hash(name);
		if (strcmp(cases, "enter") == 0)
			map_insert(map, name);
		else if (strcmp(cases, "leave") == 0)
			map_delete(map, name);
	}

	if (map->size <= 0)
		return (0);

	char **result;
	t_node	*curr;
    
	result = malloc(sizeof(char *) * map->size);
	for (i = 0; i < map->size; i++)
		result[i] = malloc(sizeof(char) * 6);
	
    j = 0;
	for (i = 0; i < MOD; i++)
	{
		if (map->map[i] != 0)
		{
			curr = map->map[i];
			while (curr)
			{
				result[j] = curr->key;
				j++;
				curr = curr->next;
			}
		}
	}

	qsort(result, map->size, sizeof(result[0]), str_cmp);

	for (i = 0; i < map->size; i++)
		printf("%s\n", result[i]);
	return (0);
}

djm03178 3년 전 0

삽입할 때 next에 연결해주는 부분이 없는 것 같습니다.

lkgsns 3년 전 0

답변 정말 감사합니다.

map_insert함수 말씀이신가요?? curr = curr->next 로 이어주었다고 생각하는데 아닌가요?

djm03178 3년 전 0

그건 curr이라는 포인터가 링크드 리스트를 따라서 진행하는 것뿐입니다. 리스트 자체에는 아무런 변화가 없습니다. 새로 삽입한 원소가 리스트에 끼워넣어지지를 않습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 이유를 모르겠습니다.

lkgsns 3년 전 0

djm03178 3년 전 1

djm03178 3년 전 1

lkgsns 3년 전 0

djm03178 3년 전 0

lkgsns 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말