알고리즘 풀이/Java
[알고리즘] 산타의 선물 공장 2
Dong's Universe
2024. 4. 1. 23:00
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static final int MAX_SIZE = 100_001;
static Node[] head = new Node[MAX_SIZE];
static Node[] tail = new Node[MAX_SIZE];
static int[] size = new int[MAX_SIZE];
static Node[] nodes = new Node[MAX_SIZE];
static BufferedReader br;
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine());
for (int i = 1; i <= q; i++) {
st = new StringTokenizer(br.readLine());
int cmd = Integer.parseInt(st.nextToken());
switch (cmd) {
case 100:
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
init(n, m);
break;
case 200:
int m_src = Integer.parseInt(st.nextToken());
int m_dst = Integer.parseInt(st.nextToken());
sb.append(moveAll(m_src, m_dst)).append("\n");
break;
case 300:
m_src = Integer.parseInt(st.nextToken());
m_dst = Integer.parseInt(st.nextToken());
sb.append(replace(m_src, m_dst)).append("\n");
break;
case 400:
m_src = Integer.parseInt(st.nextToken());
m_dst = Integer.parseInt(st.nextToken());
sb.append(divide(m_src, m_dst)).append("\n");
break;
case 500:
int p_num = Integer.parseInt(st.nextToken());
sb.append(getGiftInfo(p_num)).append("\n");
break;
case 600:
int b_num = Integer.parseInt(st.nextToken());
sb.append(getBeltInfo(b_num)).append("\n");
break;
}
}
System.out.println(sb);
// init(3, 5);
// addLast(1, 1);
// addLast(1, 2);
// addLast(1, 3);
// addLast(2, 4);
// addLast(2, 5);
// print(1);
// print(2);
// moveAll(1, 2);
// print(2);
// moveAll(3, 2);
// print(2);
// pollFirst(2);
// print(2);
// pollFirst(1);
// print(1);
// divide(2, 1);
// print(2);
// print(1);
// replace(1, 2);
// print(2);
// print(1);
// moveAll(1, 2);
// replace(1, 2);
// print(2);
// print(1);
// System.out.println(getGiftInfo(2));
}
private static void init(int n, int m) {
for (int i = 1; i <= n; i++) {
head[i] = new Node();
tail[i] = new Node();
head[i].next = tail[i];
tail[i].prev = head[i];
}
for (int i = 1; i <= m; i++) {
int beltId = Integer.parseInt(st.nextToken());
Node node = addLast(beltId, i);
nodes[i] = node;
}
}
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 Node addFirst(int beltId, Node node) {
node.next = head[beltId].next;
node.next.prev = node;
head[beltId].next = node;
node.prev = head[beltId];
size[beltId]++;
return node;
}
private static Node addLast(int beltId, int id) {
Node node = new Node();
node.id = id;
node.prev = tail[beltId].prev;
node.prev.next = node;
tail[beltId].prev = node;
node.next = tail[beltId];
size[beltId]++;
return node;
}
private static Node pollFirst(int beltId) {
if (head[beltId].next == tail[beltId]) {
return null;
} else {
Node temp = head[beltId].next;
temp.next.prev = head[beltId];
head[beltId].next = temp.next;
temp.next = null;
temp.prev = null;
size[beltId]--;
return temp;
}
}
private static int moveAll(int m_src, int m_dst) {
Node srcHead = head[m_src];
Node dstHead = head[m_dst];
Node srcTail = tail[m_src];
Node dstTail = tail[m_dst];
if (srcHead.next != srcTail) {
srcTail.prev.next = dstHead.next;
dstHead.next.prev = srcTail.prev;
srcHead.next.prev = dstHead;
dstHead.next = srcHead.next;
srcHead.next = srcTail;
srcTail.prev = srcHead;
}
size[m_dst] += size[m_src];
size[m_src] = 0;
return size[m_dst];
}
private static int replace(int m_src, int m_dst) {
Node srcHead = head[m_src];
Node dstHead = head[m_dst];
Node srcTail = tail[m_src];
Node dstTail = tail[m_dst];
if (srcHead.next == srcTail && dstHead.next == dstTail) {
return 0;
} else if (srcHead.next == srcTail) {
Node node = pollFirst(m_dst);
addFirst(m_src, node);
} else if (dstHead.next == dstTail) {
Node node = pollFirst(m_src);
addFirst(m_dst, node);
} else {
Node node1 = pollFirst(m_src);
Node node2 = pollFirst(m_dst);
addFirst(m_dst, node1);
addFirst(m_src, node2);
}
return size[m_dst];
}
private static int divide(int m_src, int m_dst) {
int l = size[m_src] / 2;
Deque<Node> deque = new ArrayDeque<>();
for (int i = 0; i < l; i++) {
Node node = pollFirst(m_src);
deque.addFirst(node);
}
for (int i = 0; i < l; i++) {
addFirst(m_dst, deque.pollFirst());
}
return size[m_dst];
}
private static int getGiftInfo(int p_num) {
Node node = nodes[p_num];
Node prev = node.prev;
Node next = node.next;
int p = -1;
int n = -1;
if (prev.id != 0) {
p = prev.id;
}
if (next.id != 0) {
n = next.id;
}
return p + 2 * n;
}
private static int getBeltInfo(int b_num) {
int h = head[b_num].next == tail[b_num] ? -1 : head[b_num].next.id;
int t = head[b_num].next == tail[b_num] ? -1 : tail[b_num].prev.id;
int s = size[b_num];
return h + 2 * t + 3 * s;
}
static class Node {
int id;
Node prev;
Node next;
public Node(int id, Node prev, Node next) {
this.id = id;
this.prev = prev;
this.next = next;
}
public Node() {
}
}
}나의 풀이
- 링크드리스트를 구현해서 풀어야 하는 문제이다
- addLast, addFirst, pollFirst 등 최소한의 기능을 하는 걸 구현하고 조합하면 된다.
- size를 늘리고 줄이는 걸 addLast에서 해주었는데 바깥에서도 중복으로 해주어서 원하는 결과가 나오지 않았다.
- head와 tail 각각에 대해 더미 노드를 만들면 구현하기가 정말 편해진다!!!!!!!!!