문제

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

---

입력

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

---

출력

500명령어에 대해 채점 대기 큐에 있는 task의 수를 한 줄에 하나씩 출력합니다.

---

풀이

제한조건

• 1 ≤ Q ≤ 50,000
• 1 ≤ N ≤ 50,000
• 1 ≤ 도메인의 길이 ≤ 19
• 1 ≤ 주어지는 서로 다른 도메인의 수 ≤ 300
• 1 ≤ 문제 ID ≤ 1,000,000,000
• 1 ≤ p ≤ N
• 1 ≤ Jid ≤ N
• 1 ≤ t ≤ 1,000,000

접근방법

시뮬레이션 + 우선순위 큐

정말 단순하지만, 실수를 디버깅하기 어려운 문제이다.
우선순위 큐를 이용해서 접근하는 문제로, 시간초과에 주의해야한다.

문제분석

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

1. 채점기 준비
2. 채점 요청
3. 채점 시도
4. 채점 종료
5. 채점 대기 큐 조회

우선 기능 구현 전, 사용할 데이터 타입에 대해서 정의해보자.
각 문제는 요청받은 시간, 우선순위, url을 가진다.
url은 다시 도메인과 문제번호로 나누어 진다.

우선순위 큐를 통해 작업을 할 예정이므로, 객체의 비교 연산을 가능하게 수정해준다.
(C++의 compare함수)
또한 url을 그대로 저장하지말고, 분해하자.
Set구조를 사용할 때, Key값이 String으로 구성된것 보다, Integer로 구성하는게 이득이다.

• 더 적은 메모리 사용
• hashcode 생성 및 비교 과정에서 이득
  그러므로 각 domain마다 대응되는 int형의 key값을 만들어 대응시키자.

static class Problem implements Comparable<Problem> {
		int time;
		int priority;
		int domainId;
		int problemId;

		Problem(int time, int priority, int domainId, int problemId) {
			this.time = time;
			this.priority = priority;
			this.domainId = domainId;
			this.problemId = problemId;
		}

		@Override
		public int compareTo(Problem o) {
			if (this.priority == o.priority)
				return this.time - o.time;
			return this.priority - o.priority;
		}
	}

또한 처음에는 1개의 우선순위 큐로 대기열을 구성했다. (시간초과)
1개의 우선순위 큐로 구성할 경우, 최악의 경우 N번을 모두 탐색해야 원하는 작업을 찾을 수 있었다. 또한 선택되지 않은 문제를 다시 집어넣는 비용도 컸다.

따라서, 각 도메인 별 우선순위큐를 별도로 생성해 두기로 했다.

static PriorityQueue<Problem>[] waitingQueue = new PriorityQueue[MAX_DOMAIN];

이제 기능 구현을 살펴보자.

1. 채점기 준비
기본적인 자료형 구성 및 초기화 작업을 해주자.
Set과 Map을 적절히 활용해 아래 동작을 할 수 있어야 한다.

• domain을 int값으로 매핑
• 실행중인 domain을 찾기위한 set
• 완전 일치 url을 찾기위한 set
• 채점기와 task를 연결하기 위한 map

2. 채점 요청
정확히 일치하는 url을 가지지 않는다면 항상 대기열에 추가된다.
각 경우를 살피며 대기열에 추가해 주자.
또한 모든 대기열 큐의 사이즈를 한 번에 관리할 수 있는 별도의 변수를 생성해서 관리하자.

3. 채점 시도
각 task는 채점될 수 없는 조건이 존재한다.
해당 조건은 도메인 종속적이므로, 도메인 별로 검사를 하는것이 빠르게 접근할 수 있는 방법이다.

각 도메인을 순회하며 가장 가능성이 높은 것을 별도의 PQ에 담는다.
PQ에서 가장 우선순위가 높은것이 채점을 시도할 Task가 된다.
Map을 통해, A번 채점기에 B번 도메인의 문제가 풀릴것임을 기록해 두자.
또한 채점이 진행될 것이므로, 대기열 Task의 수를 감소시키자.

4. 채점 종료
Map을 통해 A번 채점기에 B번 도메인의 문제가 풀리고 있음을 기록해 두었다.
따라서 Map에서 A Key를 검색하여 결과에 따라 구현해주자.

만약 유효한 경우라면, 마지막 채점 시간과 종료시간을 기준으로 gap을 구해줘야 한다.
그리고 Map에 매핑해두었던 값을 다시 초기화 해주자.

5. 채점 대기 큐 조회
전체 대기열의 수를 반환하면 된다.
대기열을 모두 순회하며 더해주는것도 방법이지만,
별도의 변수를 두고 관리하면 훨씬 빠르게 접근할 수 있다.

끝.

우선 순위 큐를 사용하는 방식이 연결리스트에 비해 훨씬 코드가 단순한것 같다.
하지만 map과 set의 활용을 더 요구하는 느낌.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

public class Main {
	static int numDomain;

	static class Problem implements Comparable<Problem> {
		int time;
		int priority;
		int domainId;
		int problemId;

		Problem(int time, int priority, int domainId, int problemId) {
			this.time = time;
			this.priority = priority;
			this.domainId = domainId;
			this.problemId = problemId;
		}

		@Override
		public int compareTo(Problem o) {
			if (this.priority == o.priority)
				return this.time - o.time;
			return this.priority - o.priority;
		}
	}

	final static int MAX_DOMAIN = 301;
	static int waitingQueueSize;
	static PriorityQueue<Problem>[] waitingQueue = new PriorityQueue[MAX_DOMAIN];
	static PriorityQueue<Integer> machineQueue = new PriorityQueue<>();
	static Map<String, Integer> domainIdMap = new HashMap<>();
	static Set<Integer>[] domainPIdSet = new Set[MAX_DOMAIN];

	static Map<Integer, Integer> runDomainMap = new HashMap<>();
	static Set<Integer> runDomainSet = new HashSet<>();

	static int[] lastStart, diff;
	static int N, Q;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Q = stoi(in.readLine());

		for (int tc = 0; tc < Q; ++tc) {
			String[] inputs = in.readLine().split(" ");
			switch (stoi(inputs[0])) {
				case 100:
					readyState(inputs);
					break;
				case 200:
					requestJudge(inputs);
					break;
				case 300:
					tryJudge(inputs);
					break;
				case 400:
					endTest(inputs);
					break;
				case 500:
					findWating(inputs);
					break;
				default:
					break;
			}
		}
		System.out.println(sb);
	}

	private static void readyState(String[] inputs) {
		N = stoi(inputs[1]);

		for (int i = 0; i < N; ++i) {
			machineQueue.add(i + 1);
		}
		lastStart = new int[MAX_DOMAIN];
		diff = new int[MAX_DOMAIN];
		for (int i = 0; i < MAX_DOMAIN; ++i) {
			domainPIdSet[i] = new HashSet<>();
			waitingQueue[i] = new PriorityQueue<>();
		}
		waitingQueueSize = 0;
		numDomain = 0;
		String[] split = inputs[2].split("/");

		domainIdMap.put(split[0], numDomain);
		domainPIdSet[numDomain].add(stoi(split[1]));
		waitingQueue[numDomain].add(new Problem(0, 1, numDomain, stoi(split[1])));
		waitingQueueSize++;
		numDomain++;
	}

	private static void requestJudge(String[] inputs) {
		int t = stoi(inputs[1]);
		int p = stoi(inputs[2]);
		String[] split = inputs[3].split("/");
		int domainId = domainIdMap.getOrDefault(split[0], -1);
		int pid = stoi(split[1]);

		// 특정 domain 정보가 있다.
		if (domainId >= 0) {
			// 동일 url 존재함.
			if (domainPIdSet[domainId].contains(pid))
				return;

			domainPIdSet[domainId].add(pid);
		} else {
			domainId = numDomain;
			numDomain++;
			domainIdMap.put(split[0], domainId);
			domainPIdSet[domainId].add(pid);
		}
		waitingQueue[domainId].add(new Problem(t, p, domainId, pid));
		waitingQueueSize++;

	}

	private static void tryJudge(String[] inputs) {
		int t = stoi(inputs[1]);

		// 비어있는 채점기가 없음.
		if (machineQueue.isEmpty())
			return;

		PriorityQueue<Problem> pq = new PriorityQueue<>();
		for (int i = 0; i < numDomain; ++i) {
			// 대기열에 문제가 없음.
			if (waitingQueue[i].isEmpty())
				continue;
			Problem cur = waitingQueue[i].peek();

			// 채점중인 도메인이 있음
			if (runDomainSet.contains(cur.domainId))
				continue;

			// 최근에 재점한 적이 있음.
			if (t < lastStart[cur.domainId] + (3 * diff[cur.domainId]))
				continue;

			pq.add(cur);
		}

		// 현재 채점할 수 있는 문제가 없다.
		if (pq.isEmpty())
			return;

		Problem select = pq.poll();

		// 선정완료
		lastStart[select.domainId] = t;
		runDomainSet.add(select.domainId);
		domainPIdSet[select.domainId].remove(select.problemId);

		int machineId = machineQueue.poll();
		runDomainMap.put(machineId, select.domainId);
		waitingQueue[select.domainId].poll();
		waitingQueueSize--;
	}

	private static void endTest(String[] inputs) {
		int t = stoi(inputs[1]);
		int machineId = stoi(inputs[2]);

		int domainId = runDomainMap.getOrDefault(machineId, -1);
		if (domainId == -1)
			return;

		diff[domainId] = t - lastStart[domainId];
		machineQueue.add(machineId);
		runDomainSet.remove(domainId);
		runDomainMap.put(machineId, -1);
	}

	private static void findWating(String[] inputs) {
		int t = stoi(inputs[1]);
		sb.append(waitingQueueSize).append("\n");
	}

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