글 읽기 - 답이 틀리는데 반례를 알 수 있을까요 (0%/2%)

seokjeongeum 3년 전 0

입력을 받으면서 enter일 때 해시테이블에 삽입,

leave일 때 해시테이블에서 삭제하고

해시테이블을 돌면서 heap에 넣었다가 빼면서 출력하는 코드입니다

퇴근한 사람이 다시 출근하는 경우 등 질문에 있는 모든 반례는 다 통과하는 것 같은데

채점시 0%/2%에서 틀린 답으로 채점이 됩니다

반례를 알 수 있을까요

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
//strcpy, strcmp
//시험장에선 직접 구현 필요
#include<cstring>
using namespace std;

//hash 시작
//"사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다."
#define MAX_KEY 5
//사용안함
//#define MAX_DATA 0
//"첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 10^6)"
#define MAX_TABLE 1000000

typedef struct
{
	char key[MAX_KEY + 1];
	//사용안함
	//char data[MAX_DATA + 1];
}Hash;
Hash tb[MAX_TABLE];

//이름 충돌때문에 my_hash로 변경
unsigned long my_hash(const char *str)
{
	unsigned long hash = 5381;
	int c;

	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

int find(const char *key//사용 안함, char *data
)
{
	unsigned long h = my_hash(key);
	int cnt = MAX_TABLE;

	while (tb[h].key[0] != 0 && cnt--)
	{
		if (strcmp(tb[h].key, key) == 0)
		{
			//삭제하는 역할
			tb[h].key[0] = NULL;
			//사용안함
			//strcpy(data, tb[h].data);
			return 1;
		}
		h = (h + 1) % MAX_TABLE;
	}
	return 0;
}

int add(const char *key//사용안함, char *data
)
{
	unsigned long h = my_hash(key);

	while (tb[h].key[0] != 0)
	{
		if (strcmp(tb[h].key, key) == 0)
		{
			return 0;
		}

		h = (h + 1) % MAX_TABLE;
	}
	strcpy(tb[h].key, key);
	//사용안함
	//strcpy(tb[h].data, data);
	return 1;
}
//hash 끝

//heap 시작
//"첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 10^6)"
#define MAX_SIZE 1000000
//int heap[MAX_SIZE] => char* heap[MAX_SIZE]
//컴파일 에러 발생하는 int 변수를 char*로 변환
//비교 연산자를 strcmp로 변환, 사전 순의 역순으로 저장하기 위해 반대로 비교
//대입 연산자를 strcpy로 변환
char heap[MAX_SIZE][MAX_KEY + 1];
int heapSize = 0;

void heapInit(void)
{
	heapSize = 0;
}

int heapPush(char*value)
{
	if (heapSize + 1 > MAX_SIZE)
	{
		printf("queue is full!");
		return 0;
	}

	//heap[heapSize] = value;
	strcpy(heap[heapSize], value);

	int current = heapSize;
	while (current > 0 &&
		//heap[current] < heap[(current - 1) / 2]
		strcmp(heap[current], heap[(current - 1) / 2]) > 0
		)
	{
		//int temp = heap[(current - 1) / 2];
		char temp[MAX_KEY + 1];
		strcpy(temp, heap[(current - 1) / 2]);
		//heap[(current - 1) / 2] = heap[current];
		strcpy(heap[(current - 1) / 2], heap[current]);
		//heap[current] = temp;
		strcpy(heap[current], temp);
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;

	return 1;
}

//int* value => char*value
int heapPop(char*value)
{
	if (heapSize <= 0)
	{
		return -1;
	}

	//*value = heap[0];
	strcpy(value, heap[0]);
	heapSize = heapSize - 1;

	//heap[0] = heap[heapSize];
	strcpy(heap[0], heap[heapSize]);

	int current = 0;
	while (current * 2 + 1 < heapSize)
	{
		int child;
		if (current * 2 + 2 == heapSize)
		{
			child = current * 2 + 1;
		}
		else
		{
			child =
				//heap[current * 2 + 1] < heap[current * 2 + 2] 
				strcmp(heap[current * 2 + 1], heap[current * 2 + 2]) > 0
				? current * 2 + 1 : current * 2 + 2;
		}

		if (
			//heap[current] < heap[child]
			strcmp(heap[current], heap[child]) > 0
			)
		{
			break;
		}

		//int temp = heap[current];
		char temp[MAX_KEY + 1];
		strcpy(temp, heap[current]);
		//heap[current] = heap[child];
		strcpy(heap[current], heap[child]);
		//heap[child] = temp;
		strcpy(heap[child], temp);

		current = child;
	}
	return 1;
}
//heap 끝

char name[MAX_KEY + 1], enter_leave[MAX_KEY + 1];
int main(int argc, char** argv)
{
	int n;
	cin >> n;
	//hashtable에 이름 저장
	while (n > 0) {
		//scanf 앞에 빈 칸이 있으면 앞 줄 \n를 처리할 수 있음
		scanf(" %s %s", name, enter_leave);
		if (strcmp(enter_leave, "enter") == 0) {
			add(name);
		}
		if (strcmp(enter_leave, "leave") == 0) {
			find(name);
		}
		--n;
	}
	//heap에 hashtable에 저장된 이름 저장
	for (int i = 0; i < MAX_TABLE; ++i) {
		//이름이 있을 때만 저장
		if (tb[i].key[0] != 0) {
			heapPush(tb[i].key);
		}
	}
	//heap에서 꺼내면서 출력
	while (heapSize > 0) {
		heapPop(name);
		printf("%s\n", name);
	}
	return 0;
}

seokjeongeum 3년 전 0

find 함수에서 삭제하는 역할을 추가하여 오류가 났습니다

코드를 고쳐 통과했습니다

while (cnt--)
	{
		if (strcmp(tb[h].key, key) == 0)
		{
			//삭제하는 역할
			tb[h].key[0] = NULL;
			//사용안함
			//strcpy(data, tb[h].data);
			return 1;
		}
		h = (h + 1) % MAX_TABLE;
	}

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

문제

문제

출처

ICPC

답이 틀리는데 반례를 알 수 있을까요 (0%/2%)

seokjeongeum 3년 전 0

seokjeongeum 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말