https://www.codetree.ai/training-field/frequent-problems/problems/santa-gift-factory-2
1. 문제 요약
다음 6가지 기능을 제공하는 선물 공장을 설립하자.
- 공장 설립:
n개의 벨트에m개의 선물을 오름차순으로 쌓는다.- 물건 모두 옮기기:
m_src벨트의 선물을 모두m_dst벨트 맨 앞으로 옮긴다.- 앞 물건만 교체하기:
m_src벨트 맨 앞과m_dst벨트 맨 앞의 선물을 교환한다.- 물건 나누기:
m_src벨트의 앞에서floor(n/2)번째까지의 선물을m_dst벨트 맨 앞으로 옮긴다.- 선물 정보 얻기: 해당 선물의 앞 뒤 선물 번호를 얻는다.
- 벨트 정보 얻기: 해당 벨트의 맨 앞, 맨 뒤 선물 번호와 벨트 위의 전체 선물 개수를 얻는다.
단, 물건 나누기 명령은 최대 100번 주어진다.
명령의 개수 q는 최대 10만
벨트의 개수 n은 최대 10만
선물의 개수 m은 최대 10만
2. 문제 접근
선물의 개수가 최대 10만이므로 공간복잡도에서 문제가 생길 것 같지는 않다.
각 변수가 모두 최대 10만의 값을 가질 수 있으므로 시간복잡도가 이하가 되도록 해야 한다.
그런데 모든 명령은 다 훑어야 할테니, 각 명령을 에 수행할 수 있어야 한다.
벨트의 맨 앞, 맨 뒤를 확인할 수 있어야 하고, 맨 앞에 선물을 삽입 및 삭제를 수행해야 하기 때문에 덱(Deque)을 사용해 문제를 해결할 수 있을 것 같다.
그러면 덱을 사용했을 때 각 기능의 시간복잡도를 생각해보자.
- 공장 설립:
n개의 벨트에m개의 선물을 오름차순으로 쌓는다. - 상관없음- 물건 모두 옮기기:
m_src벨트의 선물을 모두m_dst벨트 맨 앞으로 옮긴다. -- 앞 물건만 교체하기:
m_src벨트 맨 앞과m_dst벨트 맨 앞의 선물을 교환한다. -- 물건 나누기:
m_src벨트의 앞에서floor(n/2)번째까지의 선물을m_dst벨트 맨 앞으로 옮긴다. -- 선물 정보 얻기: 해당 선물의 앞 뒤 선물 번호를 얻는다. -
- 벨트 정보 얻기: 해당 벨트의 맨 앞, 맨 뒤 선물 번호와 벨트 위의 전체 선물 개수를 얻는다. -
공장 설립은 처음에 딱 한 번 수행하고, 은 넘지 않기 때문에 시간복잡도가 중요하지 않다.
선물 정보 얻기는 따로 정보를 저장하는 자료구조를 사용한다면 에 수행할 수 있다.
물건 나누기는 이므로 목표로 하는 를 넘지만, 문제에 해당 명령이 최대 100번 주어진다는 조건이 있다. 따라서 최대 연산은 10만 * 100 = 1000만으로, 문제가 되지 않는다.
결국 물건 모두 옮기기 기능이 문제가 되고, 기본적으로 제공되는 덱 자료구조를 사용해서는 이 문제를 해결할 수 없다.
물건 모두 옮기기 연산은 m_src 벨트의 선물을 모두 m_dst 앞에 이동시키는 것이다. 이때, 그 순서를 유지하면서 옮긴다는 점을 고려하면 문제를 해결할 단서를 떠올릴 수 있다.
m_src벨트의 맨 끝과m_dst벨트의 맨 앞을 서로 연결할 수 있다면 문제를 해결할 수 있지 않을까?
이러한 생각은 Doubly Linked List(이중 연결 리스트)를 사용한다는 아이디어로 이어진다.
이 자료구조를 사용하면 물건 모두 옮기기 기능을 만에 수행할 수 있고, 다른 기능의 시간복잡도는 유지되기 때문에 문제를 해결할 수 있다.
다만 이러한 자료구조는 기본으로 제공되지 않기 때문에 직접 구현해야 한다.
벨트와 선물의 번호는 1부터 주어지기 때문에 자료구조의 크기를 N+1로 선언하는 것이 편리하다.
3. 풀이
위의 접근법에 따라, 다음과 같은 두 가지 자료구조를 사용해야 한다.
1. Doubly Linked List: 각각이 하나의 벨트를 나타낸다.
2. 각 선물의 앞 뒤 선물을 기록하는 배열
Doubly Linked List는 다음과 같은 연산을 제공해야 한다.
- 맨 앞, 맨 뒤의 값을 읽기(
벨트 정보 얻기)- 맨 앞의 값을 꺼내기(
앞 물건만 교체하기&물건 나누기)- 맨 앞, 맨 뒤에 값을 넣기(
공장 설립&앞 물건만 교체하기)- 전체 길이 얻기(
벨트 정보 얻기)- 두
Doubly Linked List를 합치기(물건 모두 옮기기&물건 나누기)
원래 Doubly Linked List는 앞 뒤를 가리키는 Node로 구성되지만, 여기서는 선물 정보 얻기 기능을 위해 앞 뒤 정보를 얻는 자료구조(배열)가 필요하다는 점을 감안하여 Doubly Linked List가 해당 배열의 인덱스 값을 가지도록 구현하여 메모리를 아낄 수 있다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static Node[] nodes;
public static DoublyLinkedList[] belts;
static int n, m;
static int[] beltNumOfGift;
// 해당 노드의 값과 앞 뒤 값을 나타내는 클래스
public static class Node {
int value;
int prev;
int next;
// 기본값은 -1로 설정
Node(int value) {
this.value = value;
this.prev = -1;
this.next = -1;
}
}
// doubly linked list를 구현하는 클래스
public static class DoublyLinkedList {
int size;
int head;
int tail;
DoublyLinkedList() {
this.size = 0;
this.head = -1;
this.tail = -1;
}
// 맨 앞에 값 넣기
public void addFirst(int value) {
// 만약 사이즈가 0이라면 새로 생성해야 한다.
if (this.size == 0) {
this.head = value;
this.tail = value;
this.size++;
return;
}
// 기존에 node가 존재했다면 head를 변경한다.
nodes[this.head].prev = value;
nodes[value].next = this.head;
this.head = value;
this.size++;
}
// 맨 뒤에 값 넣기
public void addLast(int value) {
// 만약 사이즈가 0이라면 새로 생성해야 한다.
if (this.size == 0) {
this.head = value;
this.tail = value;
this.size++;
return;
}
// 기존에 node가 존재했다면 tail를 변경한다.
nodes[this.tail].next = value;
nodes[value].prev = this.tail;
this.tail = value;
this.size++;
}
// 맨 앞에 Linked List를 연결하기
public void appendFirst(DoublyLinkedList prefix) {
// 만약 넣는 list의 길이가 0이라면 그냥 놔둔다.
if (prefix.size() == 0) {
return;
}
// 만약 기존 list의 길이가 0이라면 대체된다.
else if (this.size == 0) {
this.size = prefix.size();
this.head = prefix.peekFirst();
this.tail = prefix.peekLast();
}
// 둘 다 아니라면 기존 head와 넣는 tail을 연결하고, 넣는 head가 새 head가 된다.
// 사이즈도 갱신된다.
else {
nodes[this.head].prev = prefix.peekLast();
nodes[prefix.peekLast()].next = this.head;
this.head = prefix.peekFirst();
this.size += prefix.size();
}
}
// 맨 앞의 값 읽기
public int peekFirst() {
return this.head;
}
// 맨 뒤의 값 읽기
public int peekLast() {
return this.tail;
}
// 맨 앞의 값 꺼내기
public int getFirst() {
int value = this.head; // 꺼내는 값
// 길이가 1이었다면 빈 리스트가 되므로 모두 초기화한다.
if (this.size == 1) {
this.head = -1;
this.tail = -1;
this.size--;
return value;
}
this.head = nodes[value].next; // 새로운 head
nodes[this.head].prev = -1;
nodes[value].next = -1;
this.size--; // 크기를 1 줄인다
return value;
}
// 전체 길이 구하기
public int size() {
return this.size;
}
}
// 공장 설립 함수
public static void createFactory() {
// 각 선물의 앞 뒤를 가리키는 Node 배열
nodes = new Node[m+1];
for (int i = 0; i < m+1; i++) {
nodes[i] = new Node(i);
}
// 각 벨트를 나타내는 linked list 배열
belts = new DoublyLinkedList[n+1];
for (int i = 0; i < n+1; i++) {
belts[i] = new DoublyLinkedList();
}
// 입력받은 각 선물의 벨트 번호를 훑으면서 기록함
// belts에 addLast만 해도 nodes는 자연스럽게 기록된다.
for (int giftNum = 1; giftNum < m+1; giftNum++) {
int beltNum = beltNumOfGift[giftNum];
belts[beltNum].addLast(giftNum);
}
}
// 물건 모두 옮기기
public static int takeAllGift(int m_src, int m_dst) {
// m_src의 tail과 m_dst의 head를 연결하고, m_dst의 head를 m_src의 head로 설정한다.
// m_dst의 사이즈도 다시 설정해야 한다.
// -> appendFirst 사용
belts[m_dst].appendFirst(belts[m_src]);
// m_src는 새롭게 빈 리스트를 선언한다.
belts[m_src] = new DoublyLinkedList();
// 명령 이후 m_dst 벨트의 선물 개수를 리턴
return belts[m_dst].size();
}
//앞 물건만 교체하기
public static int tradeFirst(int m_src, int m_dst) {
// 명령 이후 m_dst 벨트의 선물 개수를 리턴
// 둘 모두 사이즈가 0인 경우 -> 아무 일도 없음
if (belts[m_src].size() == 0 && belts[m_dst].size() == 0) {
return belts[m_dst].size();
}
// m_src만 사이즈가 0인 경우
else if (belts[m_src].size() == 0) {
// m_dst의 값만 꺼내서 m_src에 넣는다.
int dstHead = belts[m_dst].getFirst();
belts[m_src].addFirst(dstHead);
return belts[m_dst].size();
}
// m_dst만 사이즈가 0인 경우
else if (belts[m_dst].size() == 0) {
// m_src의 값만 꺼내서 m_dst에 넣는다.
int srcHead = belts[m_src].getFirst();
belts[m_dst].addFirst(srcHead);
return belts[m_dst].size();
}
// 사이즈가 0인 것이 없는 경우
else {
// 서로의 head를 교환한다.
int dstHead = belts[m_dst].getFirst();
int srcHead = belts[m_src].getFirst();
belts[m_src].addFirst(dstHead);
belts[m_dst].addFirst(srcHead);
return belts[m_dst].size();
}
}
//물건 나누기
public static int moveMidGift(int m_src, int m_dst) {
// 만약 m_src의 선물의 개수가 1인 경우 옮기지 않음
if (belts[m_src].size() <= 1) {
return belts[m_dst].size();
}
// m_src의 floor(n/2) 얻기
int mid = belts[m_src].size() / 2;
// 임시 linked list 선언
DoublyLinkedList prefix = new DoublyLinkedList();
// mid까지의 m_src 값을 모두 꺼내 임시 linked list에 저장한다.
for (int i = 0; i < mid; i++) {
prefix.addLast(belts[m_src].getFirst());
}
// 얻은 linked list를 m_dst 앞에 붙인다.
belts[m_dst].appendFirst(prefix);
return belts[m_dst].size();
}
// 선물 정보 얻기
public static int getGiftInfo(int p_num) {
int answer = 0;
answer += nodes[p_num].prev;
answer += nodes[p_num].next * 2;
return answer;
}
// 벨트 정보 얻기
public static int getBeltInfo(int b_num) {
int answer = 0;
answer += belts[b_num].peekFirst();
answer += belts[b_num].peekLast() * 2;
answer += belts[b_num].size() * 3;
return answer;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 명령 개수 입력 받기
int q = Integer.parseInt(br.readLine());
// 명령을 입력받고 수행하기
for (int ord = 0; ord < q; ord++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int info = Integer.parseInt(st.nextToken());
// 공장 설립
if (info == 100) {
// 입력 받기
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
beltNumOfGift = new int[m+1];
for (int i = 1; i < m+1; i++) {
beltNumOfGift[i] = Integer.parseInt(st.nextToken());
}
// 함수 호출하여 공장 설립 완료
createFactory();
}
// 물건 모두 옮기기
else if (info == 200) {
int m_src = Integer.parseInt(st.nextToken());
int m_dst = Integer.parseInt(st.nextToken());
int dstSize = takeAllGift(m_src, m_dst);
sb.append(dstSize+"\n");
}
// 앞 물건만 교체하기
else if (info == 300) {
int m_src = Integer.parseInt(st.nextToken());
int m_dst = Integer.parseInt(st.nextToken());
int dstSize = tradeFirst(m_src, m_dst);
sb.append(dstSize+"\n");
}
// 물건 나누기
else if (info == 400) {
int m_src = Integer.parseInt(st.nextToken());
int m_dst = Integer.parseInt(st.nextToken());
int dstSize = moveMidGift(m_src, m_dst);
sb.append(dstSize+"\n");
}
// 선물 정보 얻기
else if (info == 500) {
int p_num = Integer.parseInt(st.nextToken());
int giftInfo = getGiftInfo(p_num);
sb.append(giftInfo+"\n");
}
// 벨트 정보 얻기
else{
int b_num = Integer.parseInt(st.nextToken());
int beltInfo = getBeltInfo(b_num);
sb.append(beltInfo+"\n");
}
}
// 정답 출력
System.out.println(sb);
}
}4. 회고
틀렸던 이유: 물건 나누기가 floor(n/2)번째의 선물만 가져오는 것으로 이해했는데, 알고 보니 floor(n/2)번째까지의 선물을 모두 가져오는 것이었다. 문제를 제대로 읽자.
평소 알고리즘 문제를 풀 때, 여러 정보를 기록하는 자료구조가 필요한 경우에도 클래스를 따로 선언하기보다는 int[]등의 방식으로 해결했는데, 사실 클래스가 더 직관적이고, 여러 자료형을 사용할 수 있다는 이점이 있기 때문에 이러한 방법에 익숙해지는 것이 좋을 것 같다.
