글 읽기 - 반례를 알 수 있을까요?

min6093 2년 전 0

hash 사용해서 풀었는데 답이 틀렸다고 나옵니다.

반례를 알 수 있을까요?

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX_TABLE (1000100)

typedef unsigned long long int ull;

typedef struct st
{
	char name[6];
	int in;
} DB;

typedef struct st2
{
	DB* db;
	struct st2* next;
}HASH;
DB dblist[1001000]; //전체 list
DB enterList[1001000]; //남아있는 직원 

HASH POOL[MAX_TABLE];
HASH Hash[MAX_TABLE];
int pcnt;

ull hash(const char* str)
{
	ull hash = 5381;
	int c;
	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}
	return hash % MAX_TABLE;
}
void mystrcpy(char* a, char* b)
{
	while (*a++ = *b++);
	
}
int mystrcmp(const char* a, const char* b)
{
	while (*a && *a == *b)
	{
		++a;
		++b;
	}
	return *a - *b;
}
DB b[MAX_TABLE];
void merge(int start, int end)
{
	int mid, i, j, k;
	mid = (start + end) / 2;
	i = start;
	j = mid+1;
	k = 0;

	while (i <=mid && j <=end)
	{
		if (mystrcmp(enterList[i].name, enterList[j].name) > 0)
		{
			b[k++] = enterList[i++];
		}
		else
		{
			b[k++] = enterList[j++];
		}
	}
	if (i <= mid)
	{
		b[k++] = enterList[i++];
	}

	if (j <= end)
	{
		b[k++] = enterList[j++];
	}

	for (int i = start; i <= end; i++)
	{
		enterList[i] = b[i - start];
	}

}
void sort(int start, int end)
{
	int mid;
	if (start < end)
	{
		mid = (start + end) / 2;
		sort(start, mid);
		sort(mid + 1, end);
		merge(start, end);
	}
}

int main()
{
	int N, count, inCnt;
	char name[6], cmd[6];
	scanf("%d", &N);
	count = 0;
	for (int i = 0; i < N; i++)
	{
		scanf("%s %s", name, cmd);
		if (!mystrcmp(cmd, (char*)"enter"))
		{
			mystrcpy(dblist[count].name, name);
			dblist[count].in = 1;

			ull h = hash(name);
			HASH* nd = &POOL[pcnt++];
			nd->db = &dblist[count];
			nd->next = Hash[h].next;
			Hash[h].next = nd;
			count++;
		}
		else
		{
			ull h = hash(name);
			HASH* nd = Hash[h].next;
			while (nd)
			{
				if (!mystrcmp(nd->db->name, name) && nd->db->in==1)
				{
					nd->db->in = 0;
					break;
				}

				nd = nd->next;
			}

		}
	}
	inCnt = 0;
	for (int i = 0; i < pcnt; i++)
	{
		if (dblist[i].in == 1)
		{
			enterList[inCnt++] = dblist[i];
		}
	}

	sort(0, inCnt);

	for (int i = 0; i < inCnt; i++)
	{
		printf("%s\n", enterList[i].name);
	}

	return 0;
}

nahwasa 2년 전 3

hash 중복 처리가 미흡했던듯합니다.

이하 min7093님 코드로 hash값이 296213로 동일하게 나오는 몇가지 이름으로 만든 반례입니다.

14
affva enter
baaac enter
cwvyg enter
drqdi enter
emkpk enter
itpju enter
jojvw enter
kjeay enter
pldhd enter
sxnwl enter
tsibn enter
uncnp enter
wcyet enter
yuhhz enter

예상출력 :
yuhhz
wcyet
uncnp
tsibn
sxnwl
pldhd
kjeay
jojvw
itpju
emkpk
drqdi
cwvyg
baaac
affva

출력 : (애초에 14개가 출력되지 않았음)
yuhhz
wcyet
uncnp
tsibn
sxnwl
kjeay
jojvw
itpju
drqdi
drqdi
cwvyg
baaac

min6093 2년 전 1

감사합니다 공유 해주신 반례 덕분에 문제 해결 했습니다!

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

문제

문제

출처

ICPC

반례를 알 수 있을까요?

min6093 2년 전 0

nahwasa 2년 전 3

min6093 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말