알고리즘 풀이/Java
[알고리즘][X] 코드트리 채점기
Dong's Universe
2024. 3. 30. 12:23
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main3 {
static int N;
static HashMap<String, TreeSet<Task>> wait;
static StringBuilder sb = new StringBuilder();
static HashMap<String, Integer> history;
static HashMap<String, Boolean> isCal;
static PriorityQueue<Integer> idle;
static HashMap<String, Boolean> url;
static Task[] working;
static long fin;
static long tryC;
static long req;
private static void init(String u0) {
wait = new HashMap<>();
String[] result = parse(u0);
Task task = new Task(1, u0, result[0], Integer.parseInt(result[1]), 0);
if (!wait.containsKey(result[0])) {
wait.put(result[0], new TreeSet<>());
}
wait.get(result[0]).add(task);
// domain : start + 3 * gap
history = new HashMap<>();
// 쉬고 있는 애들 -> 우선순위큐, 돌고 있는 애들 -> 배열 N <= 50,000
idle = new PriorityQueue<>();
working = new Task[N + 1];
// 도메인별로 채점을 하고 있는지 상태 확인
isCal = new HashMap<>();
isCal.put(result[0], false);
// 채점대기큐 url 확인
url = new HashMap<>();
// url.put(result[0], true);
url.put(u0, true);
for (int i = 1; i <= N; i++) {
idle.add(i);
}
}
private static String[] parse(String u0) {
StringTokenizer st = new StringTokenizer(u0, "/");
String[] result = new String[2];
result[0] = st.nextToken();
result[1] = st.nextToken();
return result;
}
private static void print(int t) {
int size = 0;
for (String domain : wait.keySet()) {
size += wait.get(domain).size();
}
// System.out.println(size);
sb.append(size).append("\n");
// if (size == 6) {
// System.out.println(t);
// }
// System.out.println();
}
private static void finCal(int t, int j_id) {
long temp = System.currentTimeMillis();
// 하고 있는 작업이 아니었다면 넘어감
Task task = working[j_id];
if (task == null) {
return;
}
// 이 도메인에 대해서 채점 불가 해제
isCal.put(task.domain, false);
int gap = t - task.calStart;
int result = task.calStart + 3 * gap;
// history에 추가
history.put(task.domain, result);
// 작업 없음
working[j_id] = null;
// 쉬는 상태
idle.add(j_id);
fin += (System.currentTimeMillis() - temp);
}
private static void tryCal(int t) {
long temp = System.currentTimeMillis();
// 놀고 있는게 없다면 넘어감
if (idle.isEmpty()) {
return;
}
PriorityQueue<Task> candidates = new PriorityQueue<>();
for (String domain : wait.keySet()) {
TreeSet<Task> tasks = wait.get(domain);
if (tasks.isEmpty()) {
continue;
}
if (isCal.get(domain)) {
continue;
}
if (history.containsKey(domain) && t < history.get(domain)) {
continue;
}
candidates.add(tasks.first());
}
if (candidates.isEmpty()) {
return;
}
Task cur = candidates.peek();
wait.get(cur.domain).remove(cur);
url.put(cur.url, false);
cur.calStart = t;
isCal.put(cur.domain, true);
int calId = idle.poll();
working[calId] = cur;
tryC += System.currentTimeMillis() - temp;
}
private static void request(int t, int p, String u) {
long temp = System.currentTimeMillis();
String[] result = parse(u);
Task task = new Task(p, u, result[0], Integer.parseInt(result[1]), t);
if (!isCal.containsKey(result[0])) {
isCal.put(result[0], false);
}
if (url.containsKey(u) && url.get(u)) {
return;
}
// for (Task task2 : wait) {
// if (task2.url.equals(task.url)) {
// return;
// }
// }
// if(!wait.contains(task)) {
url.put(u, true);
if (!wait.containsKey(task.domain)) {
wait.put(task.domain, new TreeSet<>());
}
wait.get(task.domain).add(task);
// }
req += System.currentTimeMillis() - temp;
}
public static void main(String[] args) throws Exception {
System.setIn(Files.newInputStream(Paths.get("src/codetree/cal/input.txt")));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int Q = Integer.parseInt(st.nextToken());
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int cmd = Integer.parseInt(st.nextToken());
int t = -1;
switch (cmd) {
case 100:
N = Integer.parseInt(st.nextToken());
String u0 = st.nextToken();
init(u0);
break;
case 200:
t = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
String u = st.nextToken();
request(t, p, u);
break;
case 300:
t = Integer.parseInt(st.nextToken());
tryCal(t);
break;
case 400:
t = Integer.parseInt(st.nextToken());
int J_id = Integer.parseInt(st.nextToken());
finCal(t, J_id);
break;
case 500:
t = Integer.parseInt(st.nextToken());
print(t);
break;
}
}
System.out.println(sb);
// System.out.println("fin = " + fin);
// System.out.println("tryC = " + tryC);
// System.out.println("req = " + req);
}
static class Task implements Comparable<Task> {
int p;
String url;
String domain;
int id;
int waitArrival;
int calStart;
int calFinish;
public Task(int p, String url, String domain, int id, int waitArrival) {
super();
this.p = p;
this.url = url;
this.domain = domain;
this.id = id;
this.waitArrival = waitArrival;
}
@Override
public String toString() {
return "Task [p=" + p + ", url=" + url + ", domain=" + domain + ", id=" + id
+ ", waitArrival="
+ waitArrival + ", calStart=" + calStart + ", calFinish=" + calFinish + "]";
}
@Override
public int compareTo(Task o) {
if (p == o.p) {
return waitArrival - o.waitArrival;
}
return p - o.p;
}
}
}나의 풀이
- 도메인의 개수는 최대 300개이므로 도메인 별로 안되면 판단하도록 최적화를 해주었다.
- 디버깅이 힘들었는데 map key로 url을 넣어야 하는데 domain을 넣고 있었다.
- 이런건 진짜 잡기 힘드니 처음 작성할때 잘해야 한다.
- 그리고 이 문제의 경우 여러개의 맵에 대해 key의 값이 domain이기 때문에 domain을 먼저 숫자로 바꿔주고 그걸 인덱스라고 생각하면 배열로 구현할 수 있다. 근데 이게 훨씬 빠르다. 이 문제의 경우 2배 정도 더 빨랐다. 그리고 또한 key가 있는지 없는지 굳이 확인할 필요가 없었다. 또한 그렇기에 따로 초기화를 해줄 필요도 없었다.
- 이 초기화가 자동으로 되는 점을 활용하면 스위치를 켜고 끄는 것 같은 기능을 쉽게 구현할 수 있다.
- 예를 들어, 처음에는 초기화값이 false이기 때문에 스위치를 켜고자 한다면 true만 해주면 되기 때문이다. 이렇듯 불리언의 경우 많이 유리하다.
- 맵을 이걸 한다면 내가 키가 있는 지 확인하고 없으면 false로 값을 넣어주는 등 불필요한 연산이 추가된다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main4 {
static final int MAX_DOM = 301;
static int N;
static StringBuilder sb = new StringBuilder();
static HashMap<String, Integer> map = new HashMap<>();
static int domCnt;
static PriorityQueue<Task>[] wait = new PriorityQueue[MAX_DOM];
static int[] history = new int[MAX_DOM];
static boolean[] isCal = new boolean[MAX_DOM];
static PriorityQueue<Integer> idle;
static HashSet<String> url;
static Task[] working;
static long fin;
static long tryC;
static long req;
static int size;
private static void init(String u0) {
// wait = new PriorityQueue[];
String[] result = parse(u0);
Task task = new Task(1, u0, result[0], Integer.parseInt(result[1]), 0);
if (!map.containsKey(result[0])) {
map.put(result[0], domCnt++);
}
int idx = map.get(result[0]);
wait[idx] = new PriorityQueue<>();
wait[idx].add(task);
size = 1;
// domain : start + 3 * gap
// history = new HashMap<>();
// 쉬고 있는 애들 -> 우선순위큐, 돌고 있는 애들 -> 배열 N <= 50,000
idle = new PriorityQueue<>();
working = new Task[N + 1];
// 도메인별로 채점을 하고 있는지 상태 확인
isCal[idx] = false;
// 채점대기큐 url 확인
url = new HashSet<>();
// url.put(result[0], true);
url.add(u0);
for (int i = 1; i <= N; i++) {
idle.add(i);
}
}
private static String[] parse(String u0) {
StringTokenizer st = new StringTokenizer(u0, "/");
String[] result = new String[2];
result[0] = st.nextToken();
result[1] = st.nextToken();
return result;
}
private static void print(int t) {
// int size = 0;
// for (String domain : wait.keySet()) {
// size += wait.get(domain).size();
// }
// System.out.println(size);
sb.append(size).append("\n");
// if (size == 6) {
// System.out.println(t);
// }
// System.out.println();
}
private static void finCal(int t, int j_id) {
long temp = System.currentTimeMillis();
// 하고 있는 작업이 아니었다면 넘어감
Task task = working[j_id];
if (task == null) {
return;
}
int idx = map.get(task.domain);
// 이 도메인에 대해서 채점 불가 해제
isCal[idx] = false;
int gap = t - task.calStart;
int result = task.calStart + 3 * gap;
// history에 추가
history[idx] = result;
// 작업 없음
working[j_id] = null;
// 쉬는 상태
idle.add(j_id);
fin += (System.currentTimeMillis() - temp);
}
private static void tryCal(int t) {
long temp = System.currentTimeMillis();
// 놀고 있는게 없다면 넘어감
if (idle.isEmpty()) {
return;
}
PriorityQueue<Task> candidates = new PriorityQueue<>();
for (int idx = 0; idx < domCnt; idx++) {
PriorityQueue<Task> tasks = wait[idx];
if (tasks.isEmpty()) {
continue;
}
if (isCal[idx]) {
continue;
}
if (t < history[idx]) {
continue;
}
candidates.add(tasks.peek());
}
if (candidates.isEmpty()) {
return;
}
Task cur = candidates.peek();
int idx = map.get(cur.domain);
wait[idx].remove(cur);
size--;
// url.put(cur.url, false);
url.remove(cur.url);
cur.calStart = t;
isCal[idx] = true;
int calId = idle.poll();
working[calId] = cur;
tryC += System.currentTimeMillis() - temp;
}
private static void request(int t, int p, String u) {
long temp = System.currentTimeMillis();
String[] result = parse(u);
Task task = new Task(p, u, result[0], Integer.parseInt(result[1]), t);
if (!map.containsKey(result[0])) {
map.put(result[0], domCnt++);
}
int idx = map.get(result[0]);
// if (!isCal[idx]) {
// isCal[idx] = false;
// }
if (!url.add(u)) {
return;
}
// for (Task task2 : wait) {
// if (task2.url.equals(task.url)) {
// return;
// }
// }
// if(!wait.contains(task)) {
// url.put(u, true);
if (wait[idx] == null) {
wait[idx] = new PriorityQueue<>();
}
wait[idx].add(task);
size++;
// }
req += System.currentTimeMillis() - temp;
}
public static void main(String[] args) throws Exception {
System.setIn(Files.newInputStream(Paths.get("src/codetree/cal/input.txt")));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int Q = Integer.parseInt(st.nextToken());
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine());
int cmd = Integer.parseInt(st.nextToken());
int t = -1;
switch (cmd) {
case 100:
N = Integer.parseInt(st.nextToken());
String u0 = st.nextToken();
init(u0);
break;
case 200:
t = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
String u = st.nextToken();
request(t, p, u);
break;
case 300:
t = Integer.parseInt(st.nextToken());
tryCal(t);
break;
case 400:
t = Integer.parseInt(st.nextToken());
int J_id = Integer.parseInt(st.nextToken());
finCal(t, J_id);
break;
case 500:
t = Integer.parseInt(st.nextToken());
print(t);
break;
}
}
System.out.println(sb);
// System.out.println("fin = " + fin);
// System.out.println("tryC = " + tryC);
// System.out.println("req = " + req);
}
static class Task implements Comparable<Task> {
int p;
String url;
String domain;
int id;
int waitArrival;
int calStart;
int calFinish;
public Task(int p, String url, String domain, int id, int waitArrival) {
super();
this.p = p;
this.url = url;
this.domain = domain;
this.id = id;
this.waitArrival = waitArrival;
}
@Override
public String toString() {
return "Task [p=" + p + ", url=" + url + ", domain=" + domain + ", id=" + id
+ ", waitArrival="
+ waitArrival + ", calStart=" + calStart + ", calFinish=" + calFinish + "]";
}
@Override
public int compareTo(Task o) {
if (p == o.p) {
return waitArrival - o.waitArrival;
}
return p - o.p;
}
}
}