[코드트리] 산타의 선물공장 2

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/santa-gift-factory-2/description?page=3&pageSize=20

💻 문제 풀이 : C++

📌

#include <iostream>
#include <vector>
#include <unordered_map>

// #define MAX_BELT 100010

using namespace std;

struct Belt {
	int num;
	int front;
	int back;
};

struct Present {
	int prev;
	int next;
	// int belt;
};

unordered_map<int, Belt> belt;
unordered_map<int, Present> present;

void FUNC(int q)
{
	if (q == 100)
	{
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= m; i++)
		{
			int belt_idx;
			cin >> belt_idx;
			belt[belt_idx].num += 1;
			// present[i].belt = belt_idx;
			if (belt[belt_idx].num == 1)
			{
				belt[belt_idx].front = i;
				belt[belt_idx].back = i;
				present[i].prev = -1;
				present[i].next = -1;
			}
			else
			{
				present[belt[belt_idx].back].next = i;
				present[i].prev = belt[belt_idx].back;
				belt[belt_idx].back = i;
				present[i].next = -1;
			}
		}
	}
	else if (q == 200)
	{
		int from, to;
		cin >> from >> to;
		
		if (belt[from].front <= 0)
		{
			belt[from] = { 0, -1, -1 };
			cout << belt[to].num << endl;
			return;
		}
		else if (belt[to].front <= 0)
		{
			belt[to].num += belt[from].num;
			belt[from].num = 0;

			belt[to].front = belt[from].front;
			belt[to].back = belt[from].back;
		}
		else 
		{
			belt[to].num += belt[from].num;
			belt[from].num = 0;

			present[belt[to].front].prev = belt[from].back;
			present[belt[from].back].next = belt[to].front;
			belt[to].front = belt[from].front;
		}
		belt[from].front = -1;
		belt[from].back = -1;

		cout << belt[to].num << endl;
	}
	else if (q == 300)
	{
		int from, to;
		cin >> from >> to;
		int from_id = belt[from].front;
		int to_id = belt[to].front;

		// 두 벨트 다 비어있는 경우
		if (from_id <= 0 && to_id <= 0)
		{
			belt[from] = { 0, -1, -1 };
			belt[to] = { 0, -1, -1 };
			cout << 0 << endl;
			return;
		}
		else if (from_id <= 0)
		{
			belt[from] = { 0, -1, -1 };
			int to_next = present[to_id].next;
			belt[from].num += 1;
			belt[from].front = to_id;
			belt[from].back = to_id;

			belt[to].num -= 1;
			belt[to].front = to_next;

			present[to_id].next = -1;
			// present[to_id].belt = from;
			
			present[to_next].prev = -1;
		}
		else if (to_id <= 0)
		{
			belt[to] = { 0, -1, -1 };
			int from_next = present[from_id].next;
			belt[to].num += 1;
			belt[to].front = from_id;
			belt[to].back = from_id;

			belt[from].num -= 1;
			belt[from].front = from_next;

			present[from_id].next = -1;
			// present[from_id].belt = to;

			present[from_next].prev = -1;
		}
		else if (belt[from].num == 1 && belt[to].num == 1)
		{
			belt[from].front = to_id;
			belt[from].back = to_id;
			belt[to].front = from_id;
			belt[to].back = from_id;
		}
		else if (belt[from].num == 1)
		{
			int to_next = present[to_id].next;

			belt[to].front = from_id;
			belt[from].front = to_id;
			belt[from].back = to_id;

			present[to_id].next = -1;
			present[to_id].prev = -1;

			present[from_id].prev = -1;
			present[from_id].next = to_next;
			present[to_next].prev = from_id;
		}
		else if (belt[to].num == 1)
		{
			int from_next = present[from_id].next;

			belt[from].front = to_id;
			belt[to].front = from_id;
			belt[to].back = from_id;

			present[from_id].next = -1;
			present[from_id].prev = -1;

			present[to_id].prev = -1;
			present[to_id].next = from_next;
			present[from_next].prev = to_id; 
		}
		else
		{
			int from_next = present[from_id].next;
			int to_next = present[to_id].next;

			belt[from].front = to_id;
			belt[to].front = from_id;

			present[from_id].next = to_next;
			present[to_id].next = from_next;

			present[from_next].prev = to_id;
			present[to_next].prev = from_id;

			// present[from_id].belt = to;
			// present[to_id].belt = from;
		}
		cout << belt[to].num << endl;

	}
	else if (q == 400)
	{
		int from, to;
		cin >> from >> to;
		
		if (belt[from].num <= 0)
		{
			belt[from] = { 0, -1, -1 };
			cout << belt[to].num << endl;
			return;
		}
		else if (belt[from].num == 1)
		{
			cout << belt[to].num << endl;
			return;
		}
		else if (belt[to].num <= 0)
		{
			belt[to] = { 0, -1, -1 };
			int num = belt[from].num / 2;
			int idx = belt[from].front;
			// present[idx].belt = to;
			
			int i = 1;
			while (i < num) {
				// present[idx].belt = to;
				idx = present[idx].next;
				i++;
			}
			int next_id = present[idx].next;
			int front = belt[from].front;

			belt[to].num += num;
			belt[from].num -= num;

			belt[to].front = front;
			belt[to].back = idx;
			belt[from].front = next_id;

			present[idx].next = -1;
			present[next_id].prev = -1;
			cout << belt[to].num << endl;
		}
		else
		{
			int num = belt[from].num / 2;
			int idx = belt[from].front;
			// present[idx].belt = to;
			
			int i = 1;
			while (i < num) {
				// present[idx].belt = to;
				idx = present[idx].next;
				i++;
			}
			int next_id = present[idx].next;
			int front = belt[to].front;

			belt[to].num += num;
			belt[from].num -= num;

			belt[to].front = belt[from].front;
			belt[from].front = next_id;

			present[next_id].prev = -1;

			present[idx].next = front;
			present[front].prev = idx;

			cout << belt[to].num << endl;
		}
		
	}
	else if (q == 500)
	{
		int p_num;
		cin >> p_num;
		int a = present[p_num].prev;
		int b = present[p_num].next;
		cout << (a + 2 * b) << endl;
	}
	else if (q == 600)
	{
		int b_num;
		cin >> b_num;
		if (belt[b_num].num == 0)
		{
			belt[b_num] = { 0, -1, -1 };
		}
		int a = belt[b_num].front;
		int b = belt[b_num].back;
		int c = belt[b_num].num;
		cout << (a + 2 * b + 3 * c) << endl;
	}
}

int main()
{
	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++)
	{
		int order;
		cin >> order;
		FUNC(order);
	}

	return 0;
}

---

📌 memo 😊
⭐ 시간초과 유발요소를 미리 확인할것
1. vector에서 옮기기를 하려면 shift O(N) 계속 발생
=> double linked list로 O(1).
2. 검색을 하려면 O(N) 발생
=> Hash Map으로 O(1).

✔️ Platinum에서는 DoubleLinked List, Priority Queue, Hash map 등을 적극 사용!!

🔥 TestCase가 괴랄하다...
=> 경계값(0, 1, ...) 등을 꼭 체크해야함!!