알고리즘 풀이/Java
[알고리즘][X] 산타의 선물 공장
Dong's Universe
2024. 4. 2. 22:30
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
static class Node {
int id;
Node prev;
Node next;
int weight;
int beltId;
public Node(int id, int weight, int beltId) {
super();
this.id = id;
this.weight = weight;
this.beltId = beltId;
}
public Node() {
super();
id = -1;
}
}
static Node[] head;
static Node[] tail;
static int n;
static int m;
static boolean[] broken;
static HashMap<Integer, Node> nodes = new HashMap<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int Q = Integer.parseInt(st.nextToken());
for (int q = 0; q < Q; q++) {
st = new StringTokenizer(br.readLine());
int cmd = Integer.parseInt(st.nextToken());
switch (cmd) {
case 100:
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
init(n, m);
int[] temp1 = new int[n+1];
int[] temp2 = new int[n+1];
for (int i = 1; i <= n; i++) {
temp1[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= n; i++) {
temp2[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < m; i++) {
for (int j = 1; j <= n/m; j++) {
Node node = makeNode(temp1[i*n/m + j], temp2[i*n/m + j], i+1);
addLast(i+1, node);
}
}
break;
case 200:
int w_max = Integer.parseInt(st.nextToken());
int sum = down(w_max);
System.out.println(sum);
break;
case 300:
int r_id = Integer.parseInt(st.nextToken());
System.out.println(remove(r_id));
break;
case 400:
int f_id = Integer.parseInt(st.nextToken());
System.out.println(confirm(f_id));
break;
case 500:
int b_num = Integer.parseInt(st.nextToken());
System.out.println(broken(b_num));
break;
}
}
// init(12, 3);
// addLast(1, makeNode(1, 200, 1));
// addLast(1, makeNode(2, 200, 1));
// print(1);
// addLast(2, makeNode(3, 500, 2));
// addLast(2, makeNode(4, 400, 2));
// addLast(2, makeNode(5, 500, 2));
// print(1);
// print(2);
//// remove(4);
//// print(2);
// remove(6);
// confirm(4);
// print(2);
// confirm(3);
// print(2);
// confirm(3);
// print(2);
//// broken(1, 3);
//// print(2);
// print(1);
// print(2);
// System.out.println(down(400, 3));
// print(1);
// print(2);
}
private static void init(int n, int m) {
head = new Node[m +1];
tail = new Node[m +1];
broken = new boolean[m +1];
for (int i = 1; i <= m; i++) {
head[i] = new Node();
tail[i] = new Node();
head[i].next = tail[i];
tail[i].prev = head[i];
}
}
private static void print(int beltId) {
Node h = head[beltId];
while (h.next != tail[beltId]) {
h = h.next;
System.out.print(h.id + " ");
}
System.out.println();
}
private static int broken(int b_num) {
int temp;
if (!broken[b_num]) {
temp = b_num;
for (int i = 1; i < m; i++) {
int idx = (b_num + i) % m;
if (idx == 0) {
idx = m;
}
if (!broken[idx]) {
Node h = head[b_num];
Node t = tail[b_num];
while (h.next != t) {
addLast(idx, pollFirst(b_num));;
}
}
}
} else {
temp = -1;
}
broken[b_num] = true;
return temp;
}
private static int confirm(int f_id) {
Node node = nodes.get(f_id);
if (node == null || node.beltId == 0) {
return -1;
}
int beltId = node.beltId;
Node h = head[beltId];
Node t = tail[beltId];
if (h.next == node) {
return beltId;
}
Node temp1 = h.next;
Node temp2 = node.prev;
h.next = node;
node.prev = h;
temp1.prev = t.prev;
t.prev.next = temp1;
temp2.next = t;
t.prev = temp2;
return beltId;
}
private static int remove(int r_id) {
Node node = nodes.get(r_id);
if (node == null || node.beltId == 0) {
return -1;
}
node.next.prev = node.prev;
node.prev.next = node.next;
node.next = null;
node.prev = null;
node.beltId = 0;
return r_id;
}
private static int down(int w_max) {
int sum = 0;
for (int i = 1; i <= m; i++) {
Node node = peekFirst(i);
if (node == tail[i]) {
continue;
} else {
if (node.weight <= w_max) {
Node delNode = pollFirst(i);
sum += delNode.weight;
} else {
node = pollFirst(i);
addLast(i, node);
}
}
}
return sum;
}
private static Node makeNode(int id, int weight, int beltId) {
Node node = new Node(id, weight, beltId);
nodes.put(id, node);
return node;
}
private static void addLast(int beltId, Node node) {
Node h = head[beltId];
node.next = tail[beltId];
node.prev = tail[beltId].prev;
tail[beltId].prev = node;
node.prev.next = node;
node.beltId = beltId;
}
private static Node peekFirst(int beltId) {
return head[beltId].next;
}
private static Node pollFirst(int beltId) {
Node h = head[beltId];
Node t = tail[beltId];
if (h.next == t) {
return null;
}
Node temp = h.next;
h.next = temp.next;
h.next.prev = h;
temp.next = null;
temp.prev = null;
temp.beltId = 0;
return temp;
}
}- "confirm" 메소드에서 만약 내가 확인하려는 선물이 맨 앞에 있으면 기존의 코드로는 적용이 안되기 때문에 예외처리가 필요했다.
- 확실히 디버깅용 함수를 만들고 직접 간단한 테케를 돌려가며 확인해보는게 시간도 절약되고 확인이 쉽다.
- 2000 ms가 나와서 왜 느린가 했는데 알고보니 StringBuilder가 아닌 System.out.println을 쓰고 있었다. 이걸 디버깅을 위해 썼는데 바꿔주지 않았다. 조심하자!!!