문제
입력
첫 번째 줄에 명령의 수 q가 주어집니다.
두 번째 줄부터는 q개의 줄에 걸쳐 명령의 정보가 주어집니다.
출력
산타가 q개의 명령을 진행하면서 출력해야 하는 값을 한 줄에 하나씩 출력합니다.
풀이
제한조건
- 1 ≤ q ≤ 100,000
- 2 ≤ n ≤ 100,000
- 1 ≤ m ≤ 100,000
- 1 ≤ p_num ≤ m
- 1 ≤ b_num ≤ n
접근방법
시뮬레이션
선물 공장 1에 비하면, 훨씬 단순한 문제이다.
Double LinkedList를 활용하여 구현해보자.
문제분석
크게 5가지의 기능을 구현해야 한다.
1. 공장 설립
2. 물건 이동
3. 물건 교체
4. 물건 나누기
5. 선물 정보 얻기
6. 벨트 정보 얻기1. 공장 설립
단순히 입력을 받자.
연결리스트의 Node정보가 될 것이며, 필요시 빠른 접근을 위해 상자 번호와 index를 일치시켜주자.
2. 물건 이동
src의 모든 물건을 des의 앞쪽에 배치하면된다.
연결리스트를 사용중이므로
- src의 tail과 des의 head를 연결
- src의 head를 des의 head로 변경
- des의 사이즈 변경
3가지 작업을 해주면 된다.
각각이 비어있는 경우를 감안해서 구현하자.
3. 물건 교체
src와 des의 가장 앞 물건을 서로 교환한다.
LinkedList로 구현하였기에, 가장 앞 원소를 서로 꺼내고 다른 쪽 List에 추가해주는 방식으로 구현하자.
2개의 LinkedList가 둘 다 비어있는지, 하나만 데이터가 있는지를 유의하며 구현하자.
4. 물건 나누기
물건 나누기의 경우 최대 100회 주어진다.
가장 비용이 큰 함수로, 중간 지점을 찾기위해 N번의 탐색이 필요하다.
중간 지점을 기준으로 반을 잘라서 위에서 구현한 물건 이동과 동일하게 옮겨주면 된다.
5. 선물 정보 얻기
입력을 받을 때, Node의 index 정보와 상자 번호를 일치시켜두었다.
따라서 선물의 번호를 통해 index를 바로 찾을 수 있고, next와 prev를 통해 앞, 뒤의 선물 상자 번호를 알 수 있다.
수식에 맞게 단순 계산만 해주면 된다.
6. 벨트 정보 얻기
문제가 정말 친절하게 특정 벨트의 번호를 알려준다.
각 벨트마다 양방향 연결리스트로 관리중이므로, head와 tail 상자번호를 바로 찾을 수 있다.
또한 size 정보 또한 LinkedList에서 관리중이므로
이것 또한 단순 계산이다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static class Node {
int next;
int prev;
Node() {
next = -1;
prev = -1;
}
}
static class Belt {
int head;
int tail;
int size;
Belt() {
head = -1;
tail = -1;
size = 0;
}
public void addFirst(int key) {
if (size == 0) {
head = key;
tail = key;
nodes[key].prev = -1;
nodes[key].next = -1;
size++;
return;
}
nodes[head].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;
nodes[key].next = -1;
size++;
}
public int popFront() {
int key = head;
if (size == 1) {
tail = -1;
head = -1;
size--;
return key;
}
int next = nodes[head].next;
nodes[next].prev = -1;
head = next;
nodes[key].next = -1;
size--;
return key;
}
public int get(int n) {
int cur = head;
for (int i = 0; i < n; i++)
cur = nodes[cur].next;
return cur;
}
}
static Node[] nodes;
static Belt[] belts;
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:
moveProducts(inputs);
break;
case 300:
swapProduct(inputs);
break;
case 400:
devideProduct(inputs);
break;
case 500:
getProduct(inputs);
break;
case 600:
getBeltInfo(inputs);
break;
default:
break;
}
}
System.out.println(sb);
}
private static void makeFactory(String[] inputs) {
N = stoi(inputs[1]);
M = stoi(inputs[2]);
belts = new Belt[N];
for (int i = 0; i < N; ++i)
belts[i] = new Belt();
nodes = new Node[M + 1];
nodes[0] = new Node();
for (int i = 0; i < M; ++i) {
int beltNum = stoi(inputs[3 + i]) - 1;
nodes[i + 1] = new Node();
belts[beltNum].addLast(i + 1);
}
}
private static void moveProducts(String[] inputs) {
int src = stoi(inputs[1]) - 1;
int des = stoi(inputs[2]) - 1;
if (belts[src].size == 0) {
sb.append(belts[des].size).append("\n");
return;
}
if (belts[des].size == 0) {
belts[des].head = belts[src].head;
belts[des].tail = belts[src].tail;
belts[des].size = belts[src].size;
} else {
int srcLast = belts[src].tail;
int desFirst = belts[des].head;
nodes[srcLast].next = desFirst;
nodes[desFirst].prev = srcLast;
belts[des].head = belts[src].head;
belts[des].size += belts[src].size;
}
belts[src].head = -1;
belts[src].tail = -1;
belts[src].size = 0;
sb.append(belts[des].size).append("\n");
}
private static void swapProduct(String[] inputs) {
int src = stoi(inputs[1]) - 1;
int des = stoi(inputs[2]) - 1;
// 둘 다 비어있음.
if (belts[src].size == 0 && belts[des].size == 0) {
} else if (belts[src].size > 0 && belts[des].size == 0) {
belts[des].addFirst(belts[src].popFront());
} else if (belts[src].size == 0 && belts[des].size > 0) {
belts[src].addFirst(belts[des].popFront());
} else {
int value1 = belts[src].popFront();
int value2 = belts[des].popFront();
belts[des].addFirst(value1);
belts[src].addFirst(value2);
}
sb.append(belts[des].size).append("\n");
}
private static void devideProduct(String[] inputs) {
int src = stoi(inputs[1]) - 1;
int des = stoi(inputs[2]) - 1;
int size = belts[src].size;
if (size < 2) {
sb.append(belts[des].size).append("\n");
return;
}
int start = belts[src].head;
int last = belts[src].get((size / 2) - 1);
belts[src].head = nodes[last].next;
nodes[belts[src].head].prev = -1;
nodes[last].next = -1;
belts[src].size -= size / 2;
if (belts[des].size == 0) {
belts[des].head = start;
belts[des].tail = last;
belts[des].size = size / 2;
} else {
int start2 = belts[des].head;
belts[des].head = start;
nodes[last].next = start2;
nodes[start2].prev = last;
belts[des].size += size / 2;
}
sb.append(belts[des].size).append("\n");
}
private static void getProduct(String[] inputs) {
int a = -1;
int b = -1;
int key = stoi(inputs[1]);
if (nodes[key].prev != -1)
a = nodes[key].prev;
if (nodes[key].next != -1)
b = nodes[key].next;
sb.append(a + (2 * b)).append("\n");
}
private static void getBeltInfo(String[] inputs) {
int a = -1;
int b = -1;
int beltNum = stoi(inputs[1]) - 1;
if (belts[beltNum].head != -1)
a = belts[beltNum].head;
if (belts[beltNum].tail != -1)
b = belts[beltNum].tail;
sb.append((a + (2 * b)) + 3 * belts[beltNum].size).append("\n");
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}