글 읽기 - 해싱체인으로 구현시 시간 초과가 납니다 도움부탁드려요

shfshfdl 4년 전 2

안녕하세요~

우선 set을 안쓰고 풀어보고자 해싱으로 풀어보고있는데

해싱으로 우선 enter leave 처리해주고

버킷에서 남은걸 전부 string 배열로 카피후

reverse해서 출력하면 될거같아 했는데

타임아웃이나네요.. 혹시 어느부분이 타임아웃의 원인인지

좋은 솔루션이있는지 궁금합니다

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#include <string>
#define BUCKET ((1 << 10)*100)
int N;
char name[6] = { 0, };
char state[6] = { 0, };

int getHash(char * name) {
	int hash = 0;
	int i = 0;
	while (name[i] != 0) {
		hash *= 2;
		hash += (name[i] - 'A');
		i++;
	}
	return hash;
}

int m_index = 0;
struct NODE {
	NODE * next;
	NODE * prev;
	char name[6];
	NODE() {
		next = 0;
		prev = 0;
		name[0] = 0;
	}
	void setName(char * name) {
		for (int i = 0; name[i] != 0; i++) {
			this->name[i] = name[i];
		}
	}
} iMalloc[1000009];

struct LIST {
	NODE * head;
	NODE * tail;
	int size;
	LIST() {
		head = 0; tail = 0;
		size = 0;
	}

	void addNode(char * name) {
		NODE * node = newNode(name);
		if (head == 0 && tail == 0) {
			head = node;
			tail = node;
		} else {
			tail->next = node;
			node->prev = tail;
			tail = node;
		}
	}

	void delNode(char * name) {
		NODE * curr = head;
		while (curr != 0) {
			bool isMatched = true;
			for (int i = 0; name[i] != 0; i++) {
				if (curr->name[i] != name[i]) {
					isMatched = false;
					break;
				}
			}
			if (isMatched) {
				if (curr->prev == 0 && curr->next == 0) {
					head = 0; tail = 0;
				}
				else if (curr->prev != 0 && curr->next != 0) {
					curr->prev->next = curr->next;
					curr->next->prev = curr->prev;
				}
				else if (curr->prev == 0 && curr->next != 0) {
					head = curr->next;
					curr->next->prev = 0;
				}
				else if (curr->prev != 0 && curr->next == 0) {
					tail = curr->prev;
					curr->prev->next = 0;
				}
				break;
			}

			curr = curr->next;
		}
	}

	NODE * newNode(char * name) {
		NODE * node = &iMalloc[m_index++];
		node->setName(name);
		return node;
	}

};
LIST now[BUCKET];

string names[1000001];

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s %s", name, state);
		if (state[0] == 'e') {
			now[getHash(name)].addNode(name);
		}
		else {
			now[getHash(name)].delNode(name);
		}
	}
	int index = 0;
	for (int i = (BUCKET - 1); i >= 0; i--) {
		if (now[i].head != 0) {
			NODE * curr = now[i].head;
			while (curr != 0) {
				names[index++] = curr->name;
				curr = curr->next;
			}
		}
	}
	reverse(names, names + index);
	for (int i = 0; i < index; i++) {
		cout << names[i] << endl;
	}
	return 0;
}

shfshfdl 4년 전 0

질문글에서 하나 봤는데 단순히 *2를 하면 해쉬충돌이 많이나나다고하는데 좋은 해쉬를 구성하는 방법이 있을까요?

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

문제

문제

출처

ICPC

해싱체인으로 구현시 시간 초과가 납니다 도움부탁드려요

shfshfdl 4년 전 2

shfshfdl 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말