글 읽기 - 계속 틀렸다고 나오는데 반례부탁드립니다

pengin 6년 전 0

처음해보는 해시 개념을 잡고자 간단하게

'a'=1 ... 'z'=26 이렇게 번호를 매기고 각 자리수를 더하여 해시값을 구하였는데 틀렸다고 나오네요.

여러 값들을 넣어봐도 답자체는 잘나오는데 원인을 모르겟네요...

충돌은 체이닝으로 처리했어요

#include <iostream>
#define INF 26000
using namespace std;

typedef struct node {
	int x;		//문자열 열
	struct node* next;
}Node;

typedef struct head {
	Node* next;
}Head;

int r, c, index;
char input[1000][1000];
char temp[1001];
Head h[INF+1]={0};

int push(Node* n, int sum) 
{
	if(h[sum].next == NULL) {
		h[sum].next = n;
		return 1;
	} else { 
		Node* p = h[sum].next;
		while(1) 
		{
			bool flag=false;
			for(int i=index; i<r; i++) {
				if(input[index][p->x] != input[index][n->x]) { 
					flag=true;
					break;
				}
			}
			if(flag==false) {
				return 0;
			}
			if(p->next)
				p = p->next;
			else
				break;
		}
		p->next = n;
		return 2;
	}
}

Node* pop(int sum)
{
	Node* p = h[sum].next;
	h[sum].next = p->next;
	return p;
}

int main()
{
	cin.sync_with_stdio(false);
	cin >> r >> c;
	index=0;
	for(int i=0; i<r; i++) {
		cin >> temp;
		for(int j=0; j<c; j++) {
			input[i][j]=temp[j]-'a'+1;
		}
	}

	for(int i=0; i<c; i++) {
		Node* n = new Node;
		n->x = i;
		n->next = NULL;

		int tot=0;
		for(int j=0; j<r; j++) 			
			tot += input[j][i];

		if(push(n, tot)==0)  {
			cout << index << endl;
			return 0;
		}
	}

	int max = INF;
	int temp;

	for(int i=0; i<r; i++) {
		bool fin=false;
		temp = max;
		max = 0;
		for(int j=1; j<=temp; j++) { 
			if(h[j].next != NULL) {				
				Node* p = pop(j);
				int tot = j - (int)input[index][p->x];
				if(max<tot)
					max = tot;
				if(push(p, tot) == 0) {
					fin=true;
					break;
				}
				j--;
			}
		}
		if(fin==true) {
			index--;
			break;
		}
		index++;
	}
	cout << index << endl;

	return 0;
}

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

문제

문제

출처

ICPC

계속 틀렸다고 나오는데 반례부탁드립니다

pengin 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말