DS Certi (Pro) 기출 문제 - jjin-choi/study_note GitHub Wiki

□ hash table 안에는 값

  • chaining 을 통해서 probing 을 해주어 하기 때문에 이를 담고 있는 정보가 있는 값을 저장 해야 한다.
  • 객체 자체를 넣어도 되고, 이를 담고 있는 table 의 index 를 넣어 주어도 됨.
  • ex) id 범위가 1 ~ 1,000,000,000 일 경우 SIZE = 1<<16 / MASK = SIZE -1 로 하고 hash table 의 index = id & MASK 로 해주면 됨.
    • hash 안에서는 겹치는 경우가 당연히 있기 때문에 table 안에는 실제 id 값 저장

□ 특정 data(key) 정보를 빠른 시간에 검색할 때

  • key -> code -> hidx -> probing -> 원하는 정보
    • indexing (문자열, 큰 자리 수, 숫자 배열 등)
      • direct address table : 태니지, 소문자 4자
      • hash
      • 배열에 순선대로 저장 : 케이크, 총 100개 이하
  • hash key : data 의 고유 값을 나타낼 수 있는 정보로 설정
  • hash function : code 생성 (unsigned int / long long 혹은 hash index 로 변환. K 진법... )
    • 소문자만 있을 경우 : 27진법. 대소문자일 경우 53진법
  • hash size : chaining 시 최소 data 수 혹은 제곱. SIZE = 1 << x. MASK = SIZE - 1
  • linear search : 나올 수 있는 종류가 적을 때
  • direct address table : 소문자 4자리 정도이면 k 진법을 정확히 쓰면 됨. (ex. 27진법)

□ 우선순위 구하는 구조

  • linked list 입력 순 (array) ※ worst 와 average 가 차이가 있음

    • 삽입 삭제 업데이트 : O(1)
    • 쿼리 : O(n) * 쿼리 수

  • linked list 정렬 (array) ※ worst 와 average 가 거의 동일

    • 삽입 업데이트 : O(n)
    • 쿼리 : O(n) * 쿼리 수

  • heap : log n

  • heap 정렬을 쓰게 되면 구성이 안된 것을 매번 구성해야 하므로 n long n 만큼의 시간이 들기 때문에 linear search 가 낫다.

  • ex) 나튜브 문제

    • member 수 : 10,000 video 수 : 40,000
    • add() : 40,000 / remove() : 20,000 / update() : 20,000 / query : 4000, 4000
    • linked list 입력 순으로 하면
      • 삽입 삭제 업데이트 : O(1)
      • 쿼리 : O(n * 10) * 쿼리 수 = O(40,000 * 4000) = O (1억 6천 * a) + O(10 * 10000 * 40)
    • 이를 heap 으로 하면
      • 삽입 삭제 업데이트 : O(log n) * query = O (16 * 80,000)
      • 쿼리 : O(n* 10) * 쿼리 수 = O(20 * 16 * 4000)
      • 따라서 heap 으로 하는 게 좋다.

  • ex) 카톡카톡 문제

    • member 수 : 10,000

    • makeonoff() : 10,000 / 친구 관계() - 삽입 삭제 : 20,000 / 대화() : 20,000 / send() : 50,000 / getToList : 20,000 / getToPartner : 1,000

    • 우선순위 : 첫번재는 online. 두번째는 주고받은 메시지가 많은 것. 세번째는 aid 가 작을 수록 우선.

      • 우선 순위 변경 조건 : makeonof 와 + send 함수 호출 시. 따라서 모든 친구들을 돌면서 우선순위를 변경해줘야 한다.
      • makeonof 호출 수 (10,000) * 친구 수 / send 호출 수 : 50,000 / 우선 순위 query (1000) + 삽입 삭제 20,000 번

    • linked list 입력 순으로 하면

      • 삽입 삭제 업데이트 : O(1) * 쿼리 수
      • 우선순위 쿼리 : O(n * 5) * 쿼리 수 = O(5천만)

    • 이를 heap 으로 하면

      • 삽입 삭제 업데이트 : O(log n) * query = O (14 * (10,000 * n + 50000+ 20000))
      • 최악의 경우 n 은 10000 이다.
      • 쿼리 : O(n* 10) * 쿼리 수 = O(5 * 14 * 1000)

    • 이 경우에는 linked list 로 하는 게 좋다.

  • 업데이트 되는 회수가 많아서 계속 변경해줘야 한다면 heap 으로 할 경우 오래걸린다.

  • 업데이트가 적게 이루어 진다면 linear search 를 해줘도 좋다. (linked list 를 써서)

  • 우선 순위 구할 때 생각보다 linear search 로 할 경우가 많다. 생각보다 시간 안에 들어온다면 heap 쓰지 말고.. !

□ 오답 정리

  • id 값들이 범위가 너무 큰 경우에는 table 을 써보자
  • hash 와 hash 의 node 를 가리키는 linked list 를 써보자 (LRU 처럼..)
  • 위와 같이 쓸 때에는 같은 struct 를 가리키고 있으면 됨.
  • str 를 int 로 바꿀 때 늘 주의하자 !! (ex. -'a' + 1)
  • dummy 노드가 있을 때에는 for 문의 시작점이 달라지는 것도 주의
  • hash 에서 chaining 을 써야 하는 경우인지 아닌지에 따라 probing 코드 잘 짜기

□ B. 회원 참여도 분석 2

/////////// user code ///////////
const int MAX = (int)(1e5 + 5);

template <typename _type>
void _swap(_type &x, _type &y) {
	_type temp = x; x = y; y = temp; 
}

struct Member {
	int id, frequency;
};

bool _comp_0(Member x, Member y) {
	if (x.frequency == y.frequency) return x.id < y.id;
	return x.frequency < y.frequency;
}
bool _comp_1(Member x, Member y) {
	if (x.frequency == y.frequency) return x.id < y.id;
	return x.frequency < y.frequency;
}
bool _comp_2(Member x, Member y) {
	if (x.frequency == y.frequency) 
		return x.id > y.id;
	return x.frequency > y.frequency;
}

struct _priority_queue {
	int hn;
	int sum;
	int pos[MAX + MAX];
	Member heap[MAX];
	
	bool(*comp) (Member, Member);
	void init(int mode) {
		hn = 0;
		sum = 0;
		if (mode == 0) comp = _comp_0;
		if (mode == 1) comp = _comp_0;
		if (mode == 2) comp = _comp_2;
	}
	void swap(int x, int y) {
		_swap(heap[x], heap[y]);
		_swap(pos[heap[x].id], pos[heap[y].id]);
	}
	void up(int h_idx) {
		for (int c = h_idx; c > 1; c /= 2) {
			if (comp(heap[c], heap[c / 2])) swap(c, c / 2);
			else break;
		}
	}
	void down(int h_idx) {
		for (int c = h_idx * 2; c <= hn; c *= 2) {
			if (c < hn && !comp(heap[c], heap[c + 1])) c++;
			if (comp(heap[c], heap[c / 2])) swap(c, c / 2);
			else break;
		}
	}
	void push(Member newmem) {
		heap[++hn] = newmem;
		pos[newmem.id] = hn;
		up(hn);
		sum += newmem.frequency;
	}
	Member pop() {
		Member ret = heap[1];
		swap(1, hn--);
		down(1);
		sum -= ret.frequency;
		return ret;
	}
	Member erase(int h_idx) {
		Member ret = heap[h_idx];
		swap(h_idx, hn--);
		up(h_idx), down(h_idx);
		sum -= ret.frequency;
		return ret;
	}
	Member top() { return heap[1]; }
} max_pq, min_pq, front_pq, back_pq;

Member median;

// [Note!] 중간중간 median 이 바뀌므로 꼭 shift 를 해주자 
void shift_median() {
	if (front_pq.hn > back_pq.hn + 1) {
		Member out = front_pq.pop();
		back_pq.push(out);
	}
	else if (front_pq.hn < back_pq.hn) {
		Member out = back_pq.pop();
		front_pq.push(out);
	}

	median = front_pq.top();
}

void push_for_median(Member newmem) {
	if (_comp_1(newmem, median)) 
		front_pq.push(newmem);
	
	else 
		back_pq.push(newmem);

	shift_median();
}

void erase_member(Member obj) {
	min_pq.erase(min_pq.pos[obj.id]);
	max_pq.erase(max_pq.pos[obj.id]);
}

void addMember(Member obj) {
	max_pq.push(obj);
	min_pq.push(obj);

	push_for_median(obj);
}

int removeMembers(int mode) {
	if (mode == 0) {
		Member out = min_pq.pop();
		max_pq.erase(max_pq.pos[out.id]);
		
		if (_comp_1(out, median)) 
			front_pq.erase(front_pq.pos[out.id]);
		
		else 
			back_pq.erase(back_pq.pos[out.id]);
		
		shift_median();
		return out.id;
	}
	if (mode == 1) {
		if (front_pq.hn == back_pq.hn) {
			Member out_1 = front_pq.pop();
			Member out_2 = back_pq.pop();
			erase_member(out_1);
			erase_member(out_2);
			shift_median();

			return out_1.id + out_2.id;
		}
		else {
			Member out = front_pq.pop();
			erase_member(out);
			shift_median();

			return out.id;
		}
	}
	
	if (mode == 2) {
		Member out = max_pq.pop();
		min_pq.erase(min_pq.pos[out.id]);

		if (_comp_1(out, median)) 
			front_pq.erase(front_pq.pos[out.id]);
		
		else 
			back_pq.erase(back_pq.pos[out.id]);
		
		shift_median();
		return out.id;
	}
}

void getSum(int sum[]) {
	sum[0] = front_pq.sum;
	sum[1] = back_pq.sum;

	if (front_pq.hn != back_pq.hn) 
		sum[0] -= median.frequency;
}

void userInit(int memberCount, Member members[]) {
	
	max_pq.init(2);
	min_pq.init(0);
	
	front_pq.init(2);
	back_pq.init(0);
	
	for (int m = 0; m < memberCount; m++) {
		max_pq.push(members[m]);
		min_pq.push(members[m]);
	}

	front_pq.push(members[0]);
	median = members[0];

	for (int m = 1; m < memberCount; m++) 
		push_for_median(members[m]);
}

/////////// main code ///////////
#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h> 

const int IDLIMIT = (int)1e5;
const int FREQUENCYLIMIT = IDLIMIT + 1;
const int RANDMULTI = 0x694F1;
const int RANDADD = 0x26A29F;
const int RANDMOD = ~(1 << 31);
const int REMOVELIMIT = 6;
const int AVGLIMIT = 4;

struct Member {
	int id, frequency;
};

extern void userInit(int memberCount, Member members[]);
extern void addMember(Member obj);
extern int removeMembers(int mode);
extern void getSum(int sum[]);

static int randSeed;
static int memberCount, orderCount;
static int idChk[IDLIMIT];
static int passCount;
static bool continuous;

static int getRandNum(void) {
	randSeed = randSeed * RANDMULTI + RANDADD;
	return randSeed & RANDMOD;
}

static int getFrequency() {
	int frequency;
	do {
		frequency = getRandNum() % FREQUENCYLIMIT;
	} while (frequency == FREQUENCYLIMIT - 1);

	return frequency;
}

static void mainInit(int tc, int n) {
	Member members[50001];

	for (int i = 0; i < n; ++i) {
		int id = getRandNum() % IDLIMIT;
		int frequency = getFrequency();
		while (idChk[id] == tc) {
			id = (id + 1) % IDLIMIT;
		}
		idChk[id] = tc;
		members[i].id = id;
		members[i].frequency = frequency;
	}
	userInit(n, members);
}

static void addFunc(int tc) {
	Member Member;
	int id = getRandNum() % IDLIMIT;
	int frequency = getFrequency();

	while (idChk[id] == tc) {
		id = (id + 1) % IDLIMIT;
	}
	idChk[id] = tc;
	Member.id = id;
	Member.frequency = frequency;
	addMember(Member);
}

static int run(int tc) {
	passCount = 0;
	bool continuous = true;

	mainInit(tc, memberCount);
	while (orderCount--) {
		int order = getRandNum() % (REMOVELIMIT + AVGLIMIT);
		if (continuous  && order < AVGLIMIT) {
			int sum[2];
			int ansSum[2];
			getSum(sum);
			scanf("%d%d", &ansSum[0], &ansSum[1]);
			if (sum[0] == ansSum[0] && sum[1] == ansSum[1]) {
				++passCount;
			}
			continuous = false;
		}
		else {
			int K = getRandNum() % 3;
			int retId, correctId;
			retId = removeMembers(K);
			scanf("%d", &correctId);
			if (retId == correctId) {
				++passCount;
			}
			addFunc(tc);
			if (K == 1 && memberCount % 2 == 0) {
				addFunc(tc);
			}
			continuous = true;
		}
	}
	return passCount;
}

int main(void) {
	freopen("input.txt", "r", stdin);

	int TestCnt;
	int ansCount, totalScore = 0;

	scanf("%d", &TestCnt);
	setbuf(stdout, NULL);

	for (int tc = 1; tc <= TestCnt; ++tc) {
		scanf("%d%d%d%d", &randSeed, &memberCount, &orderCount, &ansCount);
		if (run(tc) == ansCount) {
			printf("#%d 100\n", tc);
			totalScore += 100;
		}
		else {
			printf("#%d 0\n", tc);
		}
	}
	printf("Total Score = %d\n", totalScore / TestCnt);
	return 0;
}

□ C. 도서관

/////////// user code ///////////
const int MAX = (int)(1e4 + 5);
const int SIZE = 1 << 14;
const int MASK = SIZE - 1;
int h_cnt, b_cnt;

int strcmp(const char* s, const char* t) {
	while (*s && *s == *t) ++s, ++t;
	return *s - *t;
}

int strlen(const char* s, int len = 0) {
	while (s[len]) ++len;
	return len;
}

void strcpy(char* dest, const char* src) {
	while ((*dest++ = *src++));
}

struct _book {
	char title[25], author[25], genre[25];
	int cnt, sum;
} books[MAX];

struct _hash {
	_book book;
	_hash* t_next;
	_hash* a_next;
	_hash* g_next;
	_hash* alloc(_book _newbook, _hash* _t_next, _hash* _a_next, _hash* _g_next) {
		book = _newbook, t_next = _t_next, a_next = _a_next, g_next = _g_next;
		return this;
	}
} h_buff[SIZE], *t_head[SIZE], *a_head[SIZE], *g_head[SIZE];

bool compare_str(_book _x, _book _y, int _type) {
	
	char x[25], y[25];

	if (_type == 1) {
		strcpy(x, _x.author);
		strcpy(y, _y.author);
	}
	if (_type == 2) {
		strcpy(x, _x.genre);
		strcpy(y, _y.genre);
	}

	int x_len = strlen(x);
	int y_len = strlen(y);

	int max = (x_len > y_len) ? x_len : y_len;

	for (int m = 0; m < max; m++) {
		if (x[m] < y[m]) return true;
		else if (x[m] > y[m]) return false;
	}

	x_len = strlen(_x.title);
	y_len = strlen(_y.title);

	max = (x_len > y_len) ? x_len : y_len;
	
	for (int m = 0; m < max; m++) {
		if (_x.title[m] < _y.title[m]) return true;
		else if (_x.title[m] > _y.title[m]) return false;
	}
}

struct _priority_queue {
	int hn;
	int type; 
	_book heap[MAX];
	
	void init(int _type) { hn = 0, type = _type; }
	void swap(_book &x, _book &y) { _book temp = x; x = y; y = temp; }
	bool comp(_book x, _book y) {
		if (x.sum == y.sum) return compare_str(x, y, type);
		return x.sum > y.sum;
	}

	void push(_book newbook) {
		heap[++hn] = newbook;
		for (int c = hn; c > 1; c /= 2) {
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
	}

	_book pop() {
		_book ret = heap[1];
		swap(heap[1], heap[hn--]);
		for (int c = 2; c <= hn; c *= 2) {
			if (c < hn && !comp(heap[c], heap[c + 1]))c++;
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
		return ret;
	}

} max_pq;

int hash_func(char str[]) {
	int ret = 0;
	for (int c = 0; str[c]; c++)
		ret = (ret * 27 + (str[c] - 'a')) & MASK;

	return ret;
}

void init() { 
	b_cnt = 0, h_cnt = 0;
	for (int s = 0; s < SIZE; s++) 
		t_head[s] = 0, a_head[s] = 0, g_head[s] = 0;
}

_hash* probing(char title[]) {
	int idx = hash_func(title);

	for (_hash* p = t_head[idx]; p; p = p->t_next) 
		if (!strcmp(p->book.title, title)) return p; 
	
	return 0;
}

void inputBook(char title[], char author[], char genre[], int cnt) {

	int t_idx = hash_func(title);
	int a_idx = hash_func(author);
	int g_idx = hash_func(genre);

	_hash* p = probing(title);

	if (!p) {
		strcpy(books[b_cnt].title, title);
		strcpy(books[b_cnt].author, author);
		strcpy(books[b_cnt].genre, genre);
		books[b_cnt].cnt = cnt;

		t_head[t_idx] = g_head[g_idx] = a_head[a_idx] = h_buff[h_cnt].alloc(books[b_cnt++], t_head[t_idx], a_head[a_idx], g_head[g_idx]);
		h_cnt++;
	}
	else 
		p->book.cnt += cnt;
}

void loanBook(char title[], int cnt) {
	_hash* p = probing(title);

	if (p) {
		int upper_cnt = (cnt >  p->book.cnt) ? p->book.cnt : cnt;
		p->book.cnt -= upper_cnt;
		p->book.sum += upper_cnt;
	}
}

int getLoanableCnt(int type, char str[]) {
	int ret = 0;

	if (type == 0) {
		int idx = hash_func(str);
		_hash* p = probing(str);
		if (!p) return 0;
		ret = p->book.cnt;
	}

	if (type == 1) {
		int idx = hash_func(str);
		for (_hash* p = a_head[idx]; p; p = p->a_next) 
			if (!strcmp(p->book.author, str)) ret += p->book.cnt;
		
	}
	if (type == 2) {
		int idx = hash_func(str);
		for (_hash* p = g_head[idx]; p; p = p->g_next)
			if (!strcmp(p->book.genre, str)) ret += p->book.cnt;
	}
	return ret;
}

void recommendBook(int type, char str[], char(*userStr)[22]) {
	
	int idx = hash_func(str);
	max_pq.init(type);
	if (type == 1) { 
		for (_hash* p = a_head[idx]; p; p = p->a_next) {
			// [Note!] hash chaining 을 쓸 때에는 꼭 실제 값과 같은지 비교해야 함. 
			if (p->book.cnt && !strcmp(p->book.author, str)) max_pq.push(p->book);
		}
		
	}
	if (type == 2) { 
		for (_hash* p = g_head[idx]; p; p = p->g_next) {
			if (p->book.cnt && !strcmp(p->book.genre, str)) max_pq.push(p->book);
		}
	}

	_book book = max_pq.pop();
	strcpy(userStr[0], book.title);
	strcpy(userStr[1], book.author);
	strcpy(userStr[2], book.genre);
}

/////////// main code ///////////
 _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

extern void init();
extern void inputBook(char title[], char author[], char genre[], int cnt);
extern void loanBook(char title[], int cnt);
extern int getLoanableCnt(int type, char str[]);
extern void recommendBook(int type, char str[], char(*userStr)[22]);

static unsigned int SEED;
static int myrand() {
	SEED = SEED * 0x694f1 + 0x26a29f;
	return SEED & 0x7fffffff;
}

static void genString(int type, char* str) {
	int maxLen[] = { 20, 10, 10 };
	int slen = myrand() % (maxLen[type] - 4) + 5;
	for (int i = 0; i < slen; ++i)
		str[i] = myrand() % 26 + 'a';
	str[slen] = 0;
}

static int mstrcmp(const char* s, const char* t) {
	while (*s && *s == *t)
		++s, ++t;
	return *s - *t;
}

static int run() {
	int QN, cmd, score = 100;
	int type, ans, cnt, ret;
	char str[3][22];
	char userStr[3][22];

	scanf("%d", &QN);

	for (int i = 1; i <= QN; ++i) {
		scanf("%d ", &cmd);
		switch (cmd) {
		case 0:
			init();
			break;
		case 1:
			for (int i = 0; i < 3; ++i) {
				scanf("%d", &SEED);
				genString(i, str[i]);
			}
			scanf("%d", &cnt);
			inputBook(str[0], str[1], str[2], cnt);
			break;
		case 2:
			scanf("%d", &SEED);
			genString(0, str[0]);
			scanf("%d", &cnt);
			loanBook(str[0], cnt);
			break;
		case 3:
			scanf("%d %d", &type, &SEED);
			genString(type, str[type]);
			scanf("%d", &ans);
			ret = getLoanableCnt(type, str[type]);
			if (ret != ans) {
				score = 0;
			}
			break;
		case 4:
			scanf("%d", &type);
			for (int i = 0; i < 3; ++i) {
				scanf("%d", &SEED);
				genString(i, str[i]);
			}
			recommendBook(type, str[type], userStr);
			if (mstrcmp(userStr[0], str[0]) != 0
				|| mstrcmp(userStr[1], str[1]) != 0
				|| mstrcmp(userStr[2], str[2]) != 0) {
				score = 0;
			}
			break;
		}
	}

	return score;
}

int main() {
	setbuf(stdout, NULL);

	freopen("input.txt", "r", stdin);
	int TC, score = 100, totalScore = 0;
	scanf("%d", &TC);

	for (int tc = 1; tc <= TC; tc++) {
		score = run();
		totalScore += score;
		printf("#Testcase %2d : %d\n", tc, score);
	}
	printf("#Total Score : %d\n", totalScore / TC);

	return 0;
}

□ D. TS 도서관

/////////// user code ///////////

/////////// main code ///////////

□ E. 태니지 게임

/////////// user code ///////////
#define THIS_CODE_IS_RUNNING
#ifdef THIS_CODE_IS_RUNNING
#define MAXLEN (5)

const int MAX_C = (int)(1e5 + 5);
const int SIZE = (27 * 27 * 27 * 27 + 5);
const int MAX_U = (int)(3e4 + 5);
int users[SIZE];
int h_cnt, u_cnt; 

struct _node {
	int id, user, server;
	int tick, point;
	_node* prev;
	_node* next;
	_node* alloc(int _id, int _user, int _server, int _tick, int _point, _node* _prev, _node* _next) {
		id = _id, user = _user, server = _server, tick = _tick, point = _point;
		prev = _prev, next = _next;
		if (prev) prev->next = this;
		if (next) next->prev = this;
		return this;
	}
	_node* erase() {
		// [Note!] 실수하지 말자.. this->next, this->prev
		if (prev) prev->next = this->next;
		if (next) next->prev = this->prev;
		return prev;
	}
} h_buff[SIZE + SIZE], *u_head[MAX_U], *c_list[MAX_C];
// u_head 의 index 는 users 테이블을 이용하여 최대 3만까지만 계산하도록 한다. 

int str_to_int(char str[]) {
	int ret = 0;
	for (int i = 0; str[i]; i++)
		// [Note!] 'a' 를 해주어야 원하는 크기 배열 사용 가능 . +1 도 해주어야 중복 제거
		ret = ret * 27 + (str[i] - 'a') + 1;
	return ret;
}


void userInit() {
	h_cnt = 0, u_cnt = 0;
	for (int c = 0; c < MAX_C; c++) c_list[c] = 0; 
	for (int u = 0; u < SIZE; u++) users[u] = 0;
	for (int u = 0; u < MAX_U; u++) u_head[u] = h_buff[h_cnt++].alloc(0, 0, 0, 0, 0, 0, 0);
}

void create(int tick, char userName[MAXLEN], char serverName[MAXLEN], int charID, int point) {
	int user = str_to_int(userName);
	int server = str_to_int(serverName);
	
	if (!users[user]) 
		users[user] = ++u_cnt;

	int u_idx = users[user];
	c_list[charID] = h_buff[h_cnt++].alloc(charID, user, server, tick, point, u_head[u_idx], u_head[u_idx]->next);
}

int destroy(int tick, int charID) {
	int ret = c_list[charID]->point;
	c_list[charID]->erase();
	c_list[charID] = 0;

	return ret;
}

void update_tick(int tick, int charID) {
	int user = c_list[charID]->user;
	int server = c_list[charID]->server;
	int point = c_list[charID]->point;
	int u_idx = users[user];

	c_list[charID]->erase(); c_list[charID] = 0;
	c_list[charID] = h_buff[h_cnt++].alloc(charID, user, server, tick, point, u_head[u_idx], u_head[u_idx]->next);
}

int numToNum(int tick, int giverID, int recieverID, int point) {
	_node* giver = c_list[giverID];
	_node* receiver = c_list[recieverID];

	if (!c_list[giverID] || !c_list[recieverID] || giver->point < point) {
		return -1;
	}
	giver->tick = tick, giver->point -= point;
	receiver->tick = tick, receiver->point += point;

	update_tick(tick, giverID);
	update_tick(tick, recieverID);

	return receiver->point;
}

int numToName(int tick, int giverID, char recieverName[MAXLEN], int point) {
	_node* giver = c_list[giverID];

	int user = str_to_int(recieverName);
	int u_idx = users[user];
	_node* receiver = u_head[u_idx]->next;

	if (!c_list[giverID] || !receiver || giver->point < point) {
		return -1;
	}
	giver->tick = tick, giver->point -= point;
	receiver->tick = tick, receiver->point += point;

	update_tick(tick, giverID);
	update_tick(tick, receiver->id);

	return receiver->point;
}

void payBonusPoint(int tick, char serverName[MAXLEN], int point) {
	int server = str_to_int(serverName);

	for (int u = 0; u <= u_cnt; u++) {
		// [Note!] dummy node 가 있을 때에는 항상 next 부터 시작 
		for (_node* p = u_head[u]->next; p; p = p->next) {
			if (p->server == server) {
				p->point += point;
				update_tick(tick, p->id);
				break;
			}
		}
	}
}

#endif

/////////// main code ///////////
#define THIS_CODE_IS_RUNNING
#ifdef THIS_CODE_IS_RUNNING

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

#define INIT            1
#define CREATE          2
#define DESTROY         3
#define NUMTONUM        4
#define NUMTONAME       5
#define BONUSPOINT      6

#define MAX_LEN 5


extern void userInit();
extern void create(int tick, char userName[MAX_LEN], char serverName[MAX_LEN], int charID, int point);
extern int destroy(int tick, int charID);
extern int numToNum(int tick, int giverID, int recieverID, int point);
extern int numToName(int tick, int giverID, char recieverName[MAX_LEN], int point);
extern void payBonusPoint(int tick, char serverName[MAX_LEN], int point);

static bool run()
{
	int commandCount;
	int order, charID, giverID, recieverID, point;
	char userName[MAX_LEN], recieverName[MAX_LEN], serverName[MAX_LEN];

	int ret = 0;
	int ans = 0;
	scanf("%d", &commandCount);
	bool correct = false;

	for (int tick = 0; tick < commandCount; ++tick)
	{
		scanf("%d", &order);

		switch (order)
		{
		case INIT:
			userInit();
			correct = true;
			break;
		case CREATE:
			scanf("%s %s %d %d", userName, serverName, &charID, &point);
			if (correct)
				create(tick, userName, serverName, charID, point);
			break;
		case DESTROY:
			scanf("%d", &charID);
			if (correct)
				ret = destroy(tick, charID);
			scanf("%d", &ans);
			if (ret != ans)
				correct = false;
			break;
		case NUMTONUM:
			scanf("%d %d %d", &giverID, &recieverID, &point);
			if (correct)
				ret = numToNum(tick, giverID, recieverID, point);
			scanf("%d", &ans);
			if (ret != ans)
				correct = false;
			break;
		case NUMTONAME:
			scanf("%d %s %d", &giverID, recieverName, &point);
			if (correct)
				ret = numToName(tick, giverID, recieverName, point);
			scanf("%d", &ans);
			if (ret != ans)
				correct = false;
			break;
		case BONUSPOINT:
			scanf("%s %d", serverName, &point);
			if (correct)
				payBonusPoint(tick, serverName, point);
			break;
		}
	}
	return correct;
}

int main()
{
	setbuf(stdout, NULL);
	freopen("input.txt", "r", stdin);

	int testCase, perfectScore;
	scanf("%d %d", &testCase, &perfectScore);

	for (int nc = 1; nc <= testCase; nc++)
	{
		int ncScore = run() ? perfectScore : 0;
		printf("#%d %d\n", nc, ncScore);
	}
	return 0;
}
#endif

□ E. 문제 명

/////////// user code ///////////

/////////// main code ///////////
⚠️ **GitHub.com Fallback** ⚠️