글 읽기 - heap + 해시

cocobo123 5년 전 0

중복되는 값 삽입을 피하기 위해 hash를 사용하고

heap 안에 N개가 있으면서 다음에 들어올 값이 heap 안의 최대값보다 크면

중복되지 않는 값이라도 heap안에 넣지 않았습니다.

그런데 85%에서 틀렸다고나오는데

짚어봐야할 부분이 어디일까요?

#include<stdio.h>
#define MaxP 101
#define MaxQ 2200000

int K, N, prime[MaxP];

//heap===================================
long long heap[MaxQ], heapIdx;

void push(long long now) {

	int nowIdx = ++heapIdx;
	int parentIdx;

	while (parentIdx = nowIdx / 2) {

		if (now < heap[parentIdx]) {
			heap[nowIdx] = heap[parentIdx];
			nowIdx = parentIdx;
		}
		else
			break;
	}
	heap[nowIdx] = now;
	return;
}

int priorityIdx(int nowIdx) {
	int leftChild = nowIdx * 2,
		rightChild = nowIdx * 2 + 1;
	if (leftChild > heapIdx)
		return 0;
	else if (leftChild == heapIdx)
		return leftChild;
	else
		return heap[leftChild] < heap[rightChild] ? leftChild : rightChild;
}

long long pop() {
	if (heapIdx == 0)return 0;
	long long popNode = heap[1];

	long long now = heap[heapIdx--];
	int nowIdx = 1,
		childIdx;

	while (childIdx = priorityIdx(nowIdx)) {
		if (heap[childIdx] < now) {
			heap[nowIdx] = heap[childIdx];
			nowIdx = childIdx;
		}
		else
			break;
	}

	heap[nowIdx] = now;
	return popNode;
}

//Hash=====================================

typedef struct node {
	long long num;
	struct node * next;
}Node;

Node hash[MaxQ], mem[MaxQ];
int memIdx;

int getKey(long long num) {
	long long key = 5381;
	for (; num; num /= 10)
		key = ((key << 5) + key + (num % 10)) % MaxQ;
	return key;
}

void pushH(int key, long long value) {
	Node * newNode = &mem[memIdx++];
	newNode->num = value;
	newNode->next = hash[key].next;
	hash[key].next = newNode;
}

int find(int key, long long value) {
	for (Node * temp = hash[key].next; temp; temp = temp->next) {
		if (temp->num == value)
			return 1;
	}
	return 0;
}
//==============================================

long long func() {

	for (int i = 0; i < K; i++) {
		int key = getKey(prime[i]);
		if (find(key, prime[i]) == 0) {
			pushH(key, prime[i]);
			push(prime[i]);
		}
	}
	long long popNode;
	long long max = 0;
	for (int cnt = 0; cnt < N; cnt++) {
		popNode = pop();

		for (int i = 0; i < K; i++) {
			long long newNode = popNode * (long long)prime[i];
			if (heapIdx > N && max <= newNode) break;

			int key = getKey(newNode);
			if (find(key, newNode) == 0) {
				pushH(key, newNode);
				push(newNode);
				max = max > newNode ? max : newNode;
			}

		}
	}
	return popNode;
}

int main() {
	scanf("%d %d", &K, &N);
	for (int i = 0; i < K; i++)
		scanf("%d", &prime[i]);
	printf("%lld\n", func());
	return 0;
}

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

문제

문제

출처

ICPC

heap + 해시

cocobo123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말