문제

https://www.codetree.ai/training-field/frequent-problems/problems/santa-gift-factory/description?page=1&pageSize=20

---

입력

첫 번째 줄에 명령의 수 q가 주어집니다.
두 번째 줄부터는 q개의 줄에 걸쳐 명령의 정보가 주어집니다.

---

출력

산타가 q개의 명령을 진행하면서 출력해야 하는 값을 한 줄에 하나씩 출력합니다.

---

풀이

제한조건

• 1 ≤ q ≤ 100,000
• 1 ≤ n ≤ 100,000
• 1 ≤ m ≤ 10, n은 항상 m의 배수
• 1 ≤ ID ≤ 1,000,000,000
• 1 ≤ W ≤ 1,000,000,000
• 1 ≤ r_id, f_id ≤ 1,000,000,000
• 1 ≤ b_num ≤ m

접근방법

시뮬레이션

22년도 하반기에 출제되었던 문제다.
A형과 B형 중간쯤의 유형과 난이도를 가진 문제이다. 어렵다..!

기존 A형 스타일의 문제에서는 순열/조합/부분집합 + 시뮬레이션의 느낌이라면,
B형 스타일의 문제는 자료구조 + 시뮬레이션으로 최적화를 요구하는 느낌이다.

B형 스타일의 문제가 계속 출제되니 이해해보자.

문제분석

크게 5가지의 기능을 구현해야 한다.

1. 공장 설립
2. 물건 하차
3. 물건 제거
4. 물건 확인
5. 벨트 고장

또한 명령이 최대 10만개, ID의 범위는 10억 그리고 시간 및 메모리의 제한으로 인하여
적당히 최적화를 하지 않으면 풀 수 없다.

어떤 자료구조를 사용해야 할까?

Double LinkedList + Map을 통해 해결해보자.
(다른 방법도 있을 수 있다..)

특정 물건을 제거하거나(기능2), 특정 물품부터 위에 존재하는 아이템을 모두 앞으로 가져오는(기능3) 작업이 존재한다.
Array 기반의 자료구조를 사용한다면 중간에 물건 하나가 사라질 때마다 비용이 매우 크다.
이는 시간초과와 빠르게 만날 수 있는 지름길이다.

중간에 있는 물건을 빠르게 추가 및 삭제하기 위해 연결리스트를 사용하자.
그 중 양방향 연결리스트를 사용해야하는 이유는
tail 정보를 가지고 있지 않다면 연결리스트의 마지막에 원소를 추가하기 위해 N번 이동해야 한다.
tail정보가 있다면, tail 뒤에 바로 추가할 수 있다.!

이제 본격적인 기능구현에 앞서 자료 구조를 정리하자.

Node{
	int id;
    int weight;
    int next;
    int prev;
}

Line{ // 양방향 연결리스트 사용
	int head; 
	int tail;
	int size;
	boolean isMalfunction; // 고장여부
    
    addFirst(int); // 추가
    addLast(int); // 추가
    popFront(); // 가장 앞 꺼내기
	remove(int); // 특정 원소 제거
    reArrange(int); // 특정 원소 기준으로 재배열
    
}

Node에서 next, prev를 Node 타입으로 선언하지 않아도 된다.

미리 필요한 수 만큼의 Node를 미리 생성해두고, 해당 Node의 index를 통해서 특정 위치에 빠르게 접근하게 만들것이므로, next와 prev를 int 타입으로 선언하고 index 정보만 담아두면, 연결리스트와 동일하게 사용가능하다.

즉 입력받은 데이터를 node[0] 부터 1,2.. 순서대로 집어놓고 index를 주소값처럼 사용한다.
또한 빠른 접근을 위해 Map 자료구조를 이용하여 물건(상자) ID로 부터 주소와 벨트를 찾아 갈 수 있도록 추가적인 자료형을 선언해주자.

Map<Integer, Integer> idIndexMap = new HashMap<>();
Map<Integer, Integer> idBeltMap = new HashMap<>();

연결리스트를 이해하고 있다면, 구현은 어렵지 않다.
추가-삭제-순서변경 과정에서 next와 prev만 잘 이어준다면 별다른 고급 알고리즘없이 구현할 수 있다.

다만, 상자의 ID - 상자의 Index - 상자가 속한 Belt 이렇게 3가지를 헷갈리지 말고
잘 이어주자.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
	static class Node {
		int id;
		int weight;
		int next;
		int prev;

		Node(int a, int b) {
			id = a;
			weight = b;
			next = -1;
			prev = -1;
		}
	}

	static class Line {
		int head;
		int tail;
		int size;
		boolean isMalfunction;

		Line() {
			head = -1;
			tail = -1;
			size = 0;
			isMalfunction = false;
		}

		public void addFirst(int key) {
			if (size == 0) {
				head = key;
				tail = key;
				size++;
				return;
			}

			nodes[tail].prev = key;
			nodes[key].next = head;
			head = key;
			size++;
		}

		public void addLast(int key) {
			if (size == 0) {
				addFirst(key);
				return;
			}

			nodes[tail].next = key;
			nodes[key].prev = tail;
			tail = key;
			size++;
		}

		public int popFront() {
			if (size == 0)
				return -1;

			int index = head;
			if (size == 1) {
				head = -1;
				tail = -1;
			} else {
				int next = nodes[head].next;
				nodes[head].next = -1;
				nodes[next].prev = -1;
				head = next;
			}
			size--;
			idBeltMap.put(nodes[index].id, -1);
			idIndexMap.put(nodes[index].id, -1);
			return index;
		}

		public void remove(int pos) {
			if (head == pos) {
				popFront();
			} else if (tail == pos) {
				int prev = nodes[tail].prev;
				nodes[tail].prev = -1;
				nodes[prev].next = -1;
				tail = prev;
				size--;
			} else {
				int prev = nodes[pos].prev;
				int next = nodes[pos].next;
				nodes[prev].next = next;
				nodes[next].prev = prev;
				size--;
			}

			idBeltMap.put(nodes[pos].id, -1);
			idIndexMap.put(nodes[pos].id, -1);
		}

		public void reArrange(int pos) {
			if (head == pos) {
				// nothing
			} else if (tail == pos) {
				int prev = nodes[tail].prev;
				nodes[tail].prev = -1;
				nodes[prev].next = -1;
				tail = prev;

				nodes[pos].next = head;
				nodes[head].prev = pos;
				head = pos;
			} else {
				int prev = nodes[pos].prev;
				int last = tail;
				int first = head;

				nodes[last].next = first;
				nodes[first].prev = last;
				nodes[prev].next = -1;
				tail = prev;
				head = pos;
			}
		}
	}

	static Map<Integer, Integer> idIndexMap = new HashMap<>();
	static Map<Integer, Integer> idBeltMap = new HashMap<>();
	static Node[] nodes;
	static Line[] lines;
	static int N, M;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = stoi(in.readLine());
		for (int tc = 0; tc < T; ++tc) {
			String[] inputs = in.readLine().split(" ");
			switch (stoi(inputs[0])) {
				case 100:
					makeFactory(inputs);
					break;
				case 200:
					unloadProduct(inputs);
					break;
				case 300:
					removeProduct(inputs);
					break;
				case 400:
					checkProduct(inputs);
					break;
				case 500:
					malfunction(inputs);
					break;
				default:
					break;
			}
		}
		System.out.println(sb);

	}

	private static void makeFactory(String[] inputs) {
		N = stoi(inputs[1]);
		M = stoi(inputs[2]);
		nodes = new Node[N];
		lines = new Line[M];
		for (int i = 0; i < M; ++i)
			lines[i] = new Line();

		for (int i = 0; i < N; ++i)
			// i번째 node는 id, weight로 구성됨.
			nodes[i] = new Node(stoi(inputs[3 + i]), stoi(inputs[3 + i + N]));

		for (int i = 0; i < N; ++i) {
			int lineNum = i / (N / M);
			lines[lineNum].addLast(i);
			idIndexMap.put(nodes[i].id, i);
			idBeltMap.put(nodes[i].id, lineNum);
		}

	}

	private static void unloadProduct(String[] inputs) {
		int limit = stoi(inputs[1]);

		int sum = 0;
		for (int i = 0; i < M; ++i) {
			if (lines[i].isMalfunction)
				continue;
			if (lines[i].size == 0)
				continue;

			int idx = lines[i].popFront();
			// 물건 하차
			if (nodes[idx].weight <= limit) {
				sum += nodes[idx].weight;
				continue;
			}

			// 재적재
			lines[i].addLast(idx);
			idIndexMap.put(nodes[idx].id, idx);
			idBeltMap.put(nodes[idx].id, i);
		}

		sb.append(sum).append("\n");
	}

	private static void removeProduct(String[] inputs) {
		int key = stoi(inputs[1]);
		int pos = idIndexMap.getOrDefault(key, -1);

		if (pos == -1) {
			sb.append(-1).append("\n");
			return;
		}

		int belt = idBeltMap.get(key);
		lines[belt].remove(pos);
		sb.append(key).append("\n");
	}

	private static void checkProduct(String[] inputs) {
		int key = stoi(inputs[1]);
		int pos = idIndexMap.getOrDefault(key, -1);

		if (pos == -1) {
			sb.append(-1).append("\n");
			return;
		}

		int belt = idBeltMap.get(key);
		lines[belt].reArrange(pos);
		sb.append(belt + 1).append("\n");
	}

	private static void malfunction(String[] inputs) {
		int n = stoi(inputs[1]);

		if (lines[n - 1].isMalfunction) {
			sb.append("-1").append("\n");
			return;
		}
		lines[n - 1].isMalfunction = true;

		int next = -1;
		for (int i = 1; i < M; ++i) {
			next = (n - 1 + i) % M;
			if (!lines[next].isMalfunction)
				break;
		}

		while (lines[n - 1].size > 0) {
			int index = lines[n - 1].popFront();
			lines[next].addLast(index);
			idIndexMap.put(nodes[index].id, index);
			idBeltMap.put(nodes[index].id, next);
		}

		sb.append(n).append("\n");
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}