유년

유년

개발자

[SWEA] 9468. 친구 추천 (C++, 라이브러리 X)

B형 실전 문제

풀이

Graph와 Bucket을 이용했다.

Graph와 Linked List를 이용해서 Edge를 만들면 Edge를 Delete할 때 해당 node의 모든 edge를 탐색하야하므로 시간초과가 난다.

그렇다고해서 N * N의 edge 배열을 만들기엔 N이 10000으로 너무 커서 메모리가 부족하다.

대안으로 Bucket을 사용했다.

64크기의 Bucket으로 Linked List를 구현하면, delete할 때에는 최대 64개의 edge만 탐색하면 되고, 필요한 메모리 공간이 N * N / 64 로 크게 준다.

실수

최대 edge의 개수가 1,000,000개 인데, 100,000개로 오타가 났다.

MAX 상수의 값을 다시 한번 체크하자.

코드 GitHub

//#include <stdio.h>

#define MAXN 10001
#define MAXE 1000001
#define BUCKET_SIZE 64
#define BUCKET_SHIFT 6


struct Edge {
	int end;
	Edge* next;

	Edge* Alloc(int _end, Edge* _next) {
		end = _end;
		next = _next;

		return this;
	}
}edges[MAXE];
int edgeCnt;

struct Node {
	Edge edges[(MAXN >> BUCKET_SHIFT) + 1];
} nodes[MAXN];

int N;

int check[MAXN];

//void showFriends() {
//	for (int n = 0; n < N; n++) {
//		printf("%d: ", n);
//		Edge* pivot = &nodes[n].edges[0];
//		while (pivot->next) {
//			if (pivot->next->end != -1) printf("%d ", pivot->next->end);
//			pivot = pivot->next;
//		}
//		printf("\n");
//	}
//}


void init(int _N) {
	edgeCnt = 0;
	N = _N + 1;
	for (int n = 1; n < N; n++) {
		for (int i = 0; i < (N >> BUCKET_SHIFT) + 1; i++) {
			if(i == (N >> BUCKET_SHIFT)) nodes[n].edges[i].Alloc(-1, nullptr);
			else nodes[n].edges[i].Alloc(-1, &nodes[n].edges[i + 1]);
		}
	}

	return;
}

void add(int id, int F, int ids[]) {
	int bnum = id >> BUCKET_SHIFT;
	
	for (int i = 0; i < F; i++) {
		int fbnum = ids[i] >> BUCKET_SHIFT;
		nodes[id].edges[fbnum].next = edges[edgeCnt++].Alloc(ids[i], nodes[id].edges[fbnum].next);
		nodes[ids[i]].edges[bnum].next = edges[edgeCnt++].Alloc(id, nodes[ids[i]].edges[bnum].next);
	}

	return;
}

void del(int id1, int id2) {
	int bnum1 = id1 >> BUCKET_SHIFT;
	int bnum2 = id2 >> BUCKET_SHIFT;

	Edge* pivot = &nodes[id1].edges[bnum2];
	while (true) {
		if (pivot->next->end == id2) break;
		pivot = pivot->next;
	}
	pivot->next = pivot->next->next;

	pivot = &nodes[id2].edges[bnum1];
	while (true) {
		if (pivot->next->end == id1) break;
		pivot = pivot->next;
	}
	pivot->next = pivot->next->next;

	return;
}

int recommend(int id, int list[]) {
	for (int n = 1; n < N; n++) {
		check[n] = 0;
	}
	check[id] = -1;

	Edge* pivot = &nodes[id].edges[0];

	while (pivot->next) {
		if (pivot->next->end != -1) {
			check[pivot->next->end] = -1;
			Edge* pivot2 = &nodes[pivot->next->end].edges[0];
			while (pivot2->next) {
				if (pivot2->next->end != -1) {
					if (check[pivot2->next->end] != -1) check[pivot2->next->end]++;
				}
				pivot2 = pivot2->next;
			}
		}
		pivot = pivot->next;
	}

	int max[5] = { 0, };
	for (int n = 1; n < N; n++) {
		int c = check[n];
		if (c > max[4]) { 
			max[4] = c;
			list[4] = n;
		}
		for (int i = 4; i > 0; i--) {
			if (max[i] > max[i - 1]) {
				int tmp = max[i];
				max[i] = max[i - 1];
				max[i - 1] = tmp;
				tmp = list[i];
				list[i] = list[i - 1];
				list[i - 1] = tmp;
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < 5; i++) {
		if (max[i] > 0) cnt++;
	}

	return cnt;
}

댓글남기기