글 읽기 - hash+binarysearch

cocobo123 5년 전 0

안녕하세요.

몇번이고 정답이 되지 않아 질문드립니다.

입력은 10^6을 넘지 않아

source[1000001] 에 \0으로 구분하여 모두 받았습니다.

줄의 맨 앞의 공백은 " %[^\n]" 으로 생략시키고

중간의 연속된 공백과 마지막의 공백 처리는 코드와 같이 해주었습니다.

N개의 코드는 10000 줄을 넘지 않는다고 하여

code[101][10001],

sourcehash[101][10001] 로 두어

각 소스코드마다의 source에 위치한 주소값을 code[i][j]에 저장하고

거기에 해당하는 hash값을 sourcehash[i][j]에 저장했습니다.

그리고 정렬한 뒤

각 오프소스마다 search하여 오픈소스의 최대값을 ans에 저장,

오픈소스의 최대값 중 최대값을 mmax에 저장하고

마지막 mmax와 같은 ans인 오픈소스의 파일명을 출력하는 식으로 했습니다.

제가 잘못 생각하고 있는 부분이 어디일까요?

#include<stdio.h>
#define Max 1000001

int makekey(char *string) {
	unsigned int key = 5381;
	for (int i = 0; string[i]; i++)
		key = ((key << 5) + key + string[i]) % Max;
	return key;
}

typedef struct node {
	char * string;
	struct node * next;
	int check;
}Node;

Node htable[Max];
Node mem[Max];
int memIdx;
char source[Max];
int code[101][10001];
int sourcehash[101][10001];
int N;

int strcmp(char * src, char * cmp) {
	for (int i = 0; src[i]; i++)
		if (src[i] != cmp[i])
			return 0;
	return 1;
}


void quick(int above, int below, int * arr,int *arr2) {
	if (above >= below)
		return;

	int left = above - 1,
		right = below + 1,
		pivot = arr[left + (right - left) / 2];

	while (left < right) {

		while (arr[++left] < pivot);
		while (pivot < arr[--right]);
		if (left >= right)break;
		int temp = arr[left];
		arr[left] = arr[right];
		arr[right] = temp;
		temp = arr2[left];
		arr2[left] = arr2[right];
		arr2[right] = temp;
	}
	quick(above, left - 1, arr,arr2);
	quick(right + 1, below, arr,arr2);

}


int search(int above, int below, int n, int i, int cnt) {
	if (code[N][i] == -1)
		return cnt;
	int left = above,
		right = below;
	int key = makekey(source + code[N][i]);

	while (left <= right) {

		int mid = left + (right - left) / 2;

		if (key < sourcehash[n][mid])
			right = mid - 1;
		else if (key > sourcehash[n][mid])
			left = mid + 1;
		else{

			Node * temp = htable[key].next;
			while (temp) {
				if (temp->check == 0 && strcmp(temp->string, source + code[N][i])) {
					temp->check = 1;
					int ans = search(above, below, n, i+1, cnt + 1);
					temp->check = 0;
					return ans;
				}
				temp = temp->next;
			}
			return cnt;
		}
	}
	return cnt;
}


int main() {
	scanf("%d", &N);
	//초기화

	for (int i = 0; i <= N; i++)
		for (int j = 0; j < 10001; j++)
			code[i][j] = -1;

	int ii = 0;
	int start = 0;
	for(int i = 0 ;i<N;i++){
		start = 0;
		while (1) {
			scanf(" %[^\n]", source + ii);
			if (strcmp(source + ii, "***END***"))
				break;
			code[i][start] = ii;


			int n = 0;
			for (n = 0; source[ii + n]; n++);

			int p = 0;
			for (p = ii; p < ii + n; p++) {
				if (source[p] == ' ') {
					int j;
					for (j = 0; source[p +1 + j] == ' '; j++);
					if (j == 0)continue;
					for (int k = p + 1; k <ii+n; k++) {
						source[k] = source[k + j];
						source[k + j] = 0;
					}
					n -= j;
				}
			}
			if (source[ii + n - 1] == ' ') {
				source[ii + n - 1] = 0;
				n--;
			}
			//hash 작업
			int key = makekey(source + ii);

			Node * newNode = &mem[memIdx++];
			newNode->string = source + ii;
			newNode->next = htable[key].next;
			htable[key].next = newNode;
			sourcehash[i][start++] = key;

			//
			ii += (n + 1);
		}
		quick(1, start - 1, sourcehash[i],code[i]);
	}
	

	start = 0;
	while (1) {
		scanf(" %[^\n]", source + ii);

		if (strcmp(source + ii, "***END***"))
			break;
		code[N][start++] = ii;

		int n = 0;
		for (n = 0; source[ii + n]; n++);

		int p = 0;
		for (p = ii; p < ii + n; p++) {
			if (source[p] == ' ') {
				int j;
				for (j = 0; source[p + 1 + j] == ' '; j++);
				if (j == 0)continue;

				for (int k = p + 1; k <ii+n; k++) {
					source[k] = source[k + j];
					source[k + j] = 0;
				}
				n -= j;
			}
		}
		if (source[ii + n - 1] == ' '){
			source[ii + n - 1] = 0;
		n--;
		}

		ii += (n + 1);
	}
	int mmax = 0;
	int ans[101];
	for (int n = 0; n < N; n++) {
		int cnt = 0;
		int max = 0;

		int l;
		for (l = 0; code[n][l] != -1; l++);
		for (int i = 0; code[N][i] != -1; i++) {
			cnt = search(1, l - 1, n, i, 0);
			max = max > cnt ? max : cnt;
		}
		ans[n] = max;
		mmax = mmax > max ? mmax : max;
	}

	printf("%d", mmax);
	if (mmax != 0) {
		for (int i = 0; i < N; i++)
			if (mmax == ans[i])
				printf(" %s", source + code[i][0]);
	}
	printf("\n");
	return 0;
}

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

문제

문제

출처

ICPC

hash+binarysearch

cocobo123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말