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

spdlqj4818 1년 전 0

chaining을 이용해서 풀어보았는데

예제는 잘 나오는데 돌려보면 틀렸다고 나오더라구요

단어의 첫 글자의 아스키 코드 값을 이용하여 알파벳이 26개니까

해쉬값이 0~25로 나올 수 있게 만들었는데

해쉬값을 설정하는 방식에서 잘못된건가 싶기도 하고...

어차피 연결리스트로 구성을 했기에 해쉬값 충돌이 일어나도 문제가 없는것이라는 생각도 들구요..

어디가 잘못되었을까요?

#define _CRT_SECURE_NO_WARNINGS

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

#define MAX 26

typedef struct _slot
{
	char str[501];
}Slot;
typedef Slot Data;

typedef struct _node
{
	Data data;
	struct _node* next;
}Node;

typedef struct _list
{
	Node* cur;
	Node* head;
}List;

int LFirst(List* p, Data* pdata)
{
	if (p->head->next == NULL)
		return 0;

	p->cur = p->head->next;
	*pdata = p->cur->data;

	return 1;
}

int LNext(List* p, Data* pdata)
{
	if (p->cur->next == NULL)
		return 0;

	p->cur = p->cur->next;
	*pdata = p->cur->data;

	return 1;
}

void Init(List* p)
{
	p->head = (Node*)malloc(sizeof(Node));
	p->head->next = NULL;
}

void Insert(List* p, char str[])
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	strcpy(newNode->data.str, str);

	newNode->next = p->head->next;
	p->head->next = newNode;
}

int Search(List* p, char str[])
{
	Data cdata;

	if (LFirst(p, &cdata))
	{
		if (!strcmp(cdata.str, str))
			return 1;
		else
		{
			if (LNext(p, &cdata))
				if (!strcmp(cdata.str, str))
					return 1;
		}
	}
	return 0;
}

int Hash(int key)
{
	return key - 97;
}

int main()
{
	char str[501];
	int i, n, m;
	int cnt = 0;
	List* p = (List*)malloc(sizeof(List) * MAX);

	for (i = 0; i < MAX; i++)
		Init(&p[i]);

	scanf("%d %d", &n, &m);
	getchar();

	for (i = 0; i < n; i++)
	{
		scanf("%s", str);

		Insert(&p[Hash(str[0])], str);
	}

	for (i = 0; i < m; i++)
	{
		scanf("%s", str);

		cnt += Search(&p[Hash(str[0])], str);
	}
	
	printf("%d", cnt);

	return 0;
}

smdtb1998 1년 전 0

반례입니다

5 11
ca
cb
cd
ce
cf

ca
cb
cd
ca
cb
cd
ca
cb
cd
ca
cb

output 0

ans 11

serch함수를 수정해야 될 거 같습니다
해시 태그가 같은 두 개만 확인하기에 ca cb cd같은 경우 확인을 하지 않아요

spdlqj4818 1년 전 0

아 그렇네요 감사합니다

LNext 함수를 while문으로 구성하니 답은 제대로 나오는데

시간초과 걸려서 통과는 안 되네요 ㅜ

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

문제

문제

출처

ICPC

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

spdlqj4818 1년 전 0

smdtb1998 1년 전 0

spdlqj4818 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말