[코드트리] 산타의 선물 공장 2 (삼성 SW 역량테스트 2022 하반기 오후 2번, B형)

삼성 A형 전체 링크

삼성 B형 전체 링크

 

2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,

A형 1문제 + B형 문제 1문제가 출제됩니다.

 

참고

- 더블 링크드 리스트 구현 (Double Linked List Tail ver)  

- BOJ 10866 : 덱 with Linked List

 

https://www.codetree.ai/training-field/frequent-problems/problems/santa-gift-factory-2

이후 설명 및 입/출력은 링크 참고

 

문제를 요약하면 다음과 같다.

 

공장 설립

- 입력 값을 처리한다.

산타의 선물 공장과 달리 상자의 번호가 100,000 이하이므로 배열에 모두 저장할 수 있다.

벨트의 뒤에 상자를 추가하기 위해 pushBack을 구현한다.

 

물건 모두 옮기기

- SRC 벨트에 있는 상자를 DST 벨트로 모두 옮긴다.

산타의 선물 공장처럼 더블 링크드 리스트를 이용해 한 번에 옮긴다.

 

앞 물건만 교체하기

- SRC 벨트 앞의 상자와 DST 벨트 앞의 상자를 바꾼다.

앞 물건만 빼기 위해 popFront를 구현하고, 앞에 물건을 추가하기 위해 pushFront를 구현한다.

 

물건 나누기

- SRC 벨트에 있는 상자 절반을 DST로 옮긴다.

해당 명령은 최대 100번만 호출되므로, 위에서 구현한 popFront를 호출하고, 다시 pushFront를 한다.

 

선물 정보 얻기

- 상자의 앞과 뒤의 번호를 구한다.

더블 링크드 리스트의 prev, next를 이용하면 된다.

 

벨트 정보 얻기

- 벨트의 앞, 뒤, 그리고 상자의 개수를 구한다.

위의 연산에서 벨트 정보를 매번 갱신해두기 때문에 쉽게 구할 수 있다.

---

구현

 

main은 다음과 같다.

입력(COMMAND)에 대해 공장 설립, 물건 모두 옮기기, 앞 물건만 교체하기 등을 실행한다.

#define FACTORY (100)
#define MOVE_ALL (200)
#define CHANGE_FRONT (300)
#define SPLIT (400)
#define GET_PRESENT (500)
#define GET_BELT (600)

...

int main(void)
{
	scanf("%d", &Q);
	for (int q = 0; q < Q; q++)
	{
		scanf("%d", &COMMAND);

		if (COMMAND == FACTORY) input();
		else if (COMMAND == MOVE_ALL)
		{
			int m_src, m_dst;
			scanf("%d %d", &m_src, &m_dst);
			moveAll(m_src, m_dst);
		}
		else if (COMMAND == CHANGE_FRONT)
		{
			int m_src, m_dst;
			scanf("%d %d", &m_src, &m_dst);
			changeFront(m_src, m_dst);
		}
		else if (COMMAND == SPLIT)
		{
			int m_src, m_dst;
			scanf("%d %d", &m_src, &m_dst);
			splitBox(m_src, m_dst);
		}
		else if (COMMAND == GET_PRESENT)
		{
			int p_num;
			scanf("%d", &p_num);
			getPresent(p_num);
		}
		else if (COMMAND == GET_BELT)
		{
			int b_num;
			scanf("%d", &b_num);
			getBelt(b_num);
		}
	}

	return 0;
}

---

공장 설립

 

링크드 리스트를 구현하기 위해 BOX의 번호(value)와 앞, 뒤의 정보를 알 수 있는 구조체를 만든다.

typedef struct st1
{
	int value;
	int prev;
	int next;
}BOX;

 

BELT는 가장 앞에 있는 BOX의 번호와 가장 뒤에 있는 BOX의 번호만 알면 된다. 

그리고 전체 박스의 개수를 count 변수에 갱신한다.

typedef struct st2
{
	int front;
	int back;
	int count;
}BELT;

 

input에서 상자가 벨트의 끝에 쌓이기 때문에 pushBack을 구현한다.

더블 링크드 리스트이지만, 덱(with Linked List)과 구현이 비슷하다. 

빈 벨트인 경우 (front = -1로 초기화), front에 boxNum을 할당하고, 해당 box의 앞은 -1(head)로 설정한다.

박스가 있는 경우는 마지막 박스 번호에 새로운 박스를 연결하면 된다.

그리고 belt의 정보를 갱신하자. (벨트의 마지막 상자와 상자 수 증가)

void pushBack(int beltNum, int boxNum)
{	
	// 빈 벨트인 경우
	if (belt[beltNum].front == -1) 
	{
		belt[beltNum].front = boxNum;
		box[boxNum].prev = -1;
	}
	else
	{
		int lastBoxNum = belt[beltNum].back;

		box[lastBoxNum].next = boxNum;
		box[boxNum].prev = lastBoxNum;		
	}

	belt[beltNum].back = boxNum;
	box[boxNum].next = -1;

	belt[beltNum].count++;
}

 

input은 다음과 같다.

void input()
{
	scanf("%d %d", &N, &M);

	for (int n = 1; n <= N; n++)
	{
		belt[n].front = belt[n].back = -1;
		belt[n].count = 0;
	}

	// M개의 물건 준비, n번 벨트에 추가 
	for (int m = 1; m <= M; m++)
	{
		int beltNum;
		
		scanf("%d", &beltNum);

		pushBack(beltNum, m);
	}
}

---

물건 모두 옮기기

물건을 모두 옮기기 위해서 m_src 벨트의 마지막 상자와 m_dst의 첫 번째 상자를 연결하면 된다.

그리고 m_dst의 첫 번째 상자를 m_src 벨트의 첫 번째 상자로 갱신하면 된다.

모두 옮긴 후, m_src 벨트를 빈 벨트로 초기화 한다.

void moveAll(int m_src, int m_dst)
{
	BELT srcBelt = belt[m_src];
	if (srcBelt.count == 0)
	{
		printf("%d\n", belt[m_dst].count);
		return;
	}

	BELT dstBelt = belt[m_dst];
	int srcFrontBox = srcBelt.front;

	if (dstBelt.count == 0) // 이동할 벨트가 빈 경우
	{
		belt[m_dst] = srcBelt;
	}
	else
	{
		int srcLastBox = srcBelt.back;
		int dstFrontBox = dstBelt.front;

		box[srcLastBox].next = dstFrontBox;
		box[dstFrontBox].prev = srcLastBox;

		belt[m_dst].front = srcFrontBox;
		belt[m_dst].count += srcBelt.count;
	}

	// srcBelt 초기화
	belt[m_src].front = -1;
	belt[m_src].back = -1;
	belt[m_src].count = 0;

	printf("%d\n", belt[m_dst].count);
}

---

앞 물건만 교체하기

pushFront와 popFront는 pushBack과 구현이 비슷하다.

벨트에 pop을 할 상자가 없다면 0을 return하도록 하였다.

void pushFront(int beltNum, int boxNum)
{
	// 빈 벨트인 경우
	if (belt[beltNum].back == -1)
	{
		belt[beltNum].back = boxNum;
		box[boxNum].next = -1;
	}
	else
	{
		int firstBoxNum = belt[beltNum].front;

		box[firstBoxNum].prev = boxNum;
		box[boxNum].next = firstBoxNum;
	}

	belt[beltNum].front = boxNum;
	box[boxNum].prev = -1;

	belt[beltNum].count++;
}

int popFront(int beltNum)
{
	if (belt[beltNum].count == 0) return 0;

	int frontBoxNum = belt[beltNum].front;
	int nextBoxNum = box[frontBoxNum].next;
	
	// 벨트에 박스가 1개인 경우
	if (nextBoxNum == -1)
	{
		belt[beltNum].front = -1;
		belt[beltNum].back = -1;
	}
	else
	{
		belt[beltNum].front = nextBoxNum;
		box[nextBoxNum].prev = -1;
	}

	belt[beltNum].count--;

	return frontBoxNum;
}

 

위의 메서드가 잘 동작하기 때문에, 각 벨트에서 상자를 popFront하고, 해당 상자를 다시 pushFront 하면 된다.

두 벨트 모두 상자가 0인 경우 (= 빈 벨트인 경우)는 0을 출력하고 종료한다.

그리고 0이 아닌 상자를 다른 벨트에 push하였다.

void changeFront(int m_src, int m_dst)
{
	int srcFrontBox = popFront(m_src);
	int dstFrontBox = popFront(m_dst);

	if (srcFrontBox == 0 && dstFrontBox == 0)
	{
		printf("0\n");
		return;
	}

	if (srcFrontBox != 0) pushFront(m_dst, srcFrontBox);
	if (dstFrontBox != 0) pushFront(m_src, dstFrontBox);

	printf("%d\n", belt[m_dst].count);
}

---

물건 나누기

앞 물건만 교체하기에서 했던 방법 그대로, 상자를 pop하고 push한다.

한 번에 이동하는 방법을 구현해도 되지만,

해당 명령은 최대 100번, 1번 호출에 최대 5만 개의 상자만 옮길 수 있으므로, 

여러 번 pop하고 push를 해도 시간 내에 완료할 수 있다.

따라서, 가운데 있는 상자를 찾아서 한 번에 옮기는 알고리즘을 굳이 구현할 필요가 없다.

void splitBox(int m_src, int m_dst)
{
	int n = belt[m_src].count;

	int moveBox[MAX] = { 0 };
	for (int i = 0; i < n / 2; i++)
	{
		int srcFrontBox = popFront(m_src);
		moveBox[i] = srcFrontBox;
	}

	for (int i = (n / 2) - 1; i >= 0; i--)
		pushFront(m_dst, moveBox[i]);

	printf("%d\n", belt[m_dst].count);
}

 

참고로 src [1, 2, 3, 4]를 dst [5, 6, 7, 8]로 옮긴다면 dst는 [1, 2, 5, 6, 7, 8]가 된다.

( [ 2, 1, 5, 6, 7, 8]이 아님에 주의 )

→ 상자를 모두 pop하고 거꾸로 push를 하도록 구현

---

선물 정보 얻기

링크드 리스트의 prev, next로 답을 구할 수 있다.

상자가 없는 경우는 head나 tail이고, 이미 -1로 설정해두었으므로 따로 처리할 필요가 없다.

void getPresent(int p_num)
{
	BOX pBox = box[p_num];
	int front = pBox.prev;
	int back = pBox.next;

	printf("%d\n", front + 2 * back);
}

---

벨트 정보 얻기

 

위와 마찬가지로 count가 0인 경우, front와 back은 -1이 되도록 구현해두었다.

void getBelt(int b_num)
{
	BELT b = belt[b_num];
	int front = b.front;
	int back = b.back;
	int count = b.count;

	printf("%d\n", front + 2 * back + 3 * count);
}

---

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (100000 + 5000)

#define FACTORY (100)
#define MOVE_ALL (200)
#define CHANGE_FRONT (300)
#define SPLIT (400)
#define GET_PRESENT (500)
#define GET_BELT (600)

int Q, COMMAND, N, M;

typedef struct st1
{
	int value;
	int prev;
	int next;
}BOX;

typedef struct st2
{
	int front;
	int back;
	int count;
}BELT;

BOX box[MAX];
BELT belt[MAX];

void printBelt(int beltNum)
{
	printf("beltNum : %d (%d ~ %d)\n", beltNum, belt[beltNum].front, belt[beltNum].back);

	if (belt[beltNum].front == -1)
	{
		printf("empty!!\n");
		return;
	}

	int boxNum = belt[beltNum].front;

	while (1)
	{
		printf("%d ", boxNum);
		boxNum = box[boxNum].next;

		if (boxNum == -1) break;
	}

	putchar('\n');
}

void printAll()
{
	for (int n = 1; n <= N; n++)
	{
		printBelt(n);
		putchar('\n');
	}
}

void pushBack(int beltNum, int boxNum)
{
	// 빈 벨트인 경우
	if (belt[beltNum].front == -1)
	{
		belt[beltNum].front = boxNum;
		box[boxNum].prev = -1;
	}
	else
	{
		int lastBoxNum = belt[beltNum].back;

		box[lastBoxNum].next = boxNum;
		box[boxNum].prev = lastBoxNum;
	}

	belt[beltNum].back = boxNum;
	box[boxNum].next = -1;

	belt[beltNum].count++;
}

void pushFront(int beltNum, int boxNum)
{
	// 빈 벨트인 경우
	if (belt[beltNum].back == -1)
	{
		belt[beltNum].back = boxNum;
		box[boxNum].next = -1;
	}
	else
	{
		int firstBoxNum = belt[beltNum].front;

		box[firstBoxNum].prev = boxNum;
		box[boxNum].next = firstBoxNum;
	}

	belt[beltNum].front = boxNum;
	box[boxNum].prev = -1;

	belt[beltNum].count++;
}

int popFront(int beltNum)
{
	if (belt[beltNum].count == 0) return 0;

	int frontBoxNum = belt[beltNum].front;
	int nextBoxNum = box[frontBoxNum].next;

	// 벨트에 박스가 1개인 경우
	if (nextBoxNum == -1)
	{
		belt[beltNum].front = -1;
		belt[beltNum].back = -1;
	}
	else
	{
		belt[beltNum].front = nextBoxNum;
		box[nextBoxNum].prev = -1;
	}

	belt[beltNum].count--;

	return frontBoxNum;
}

void input()
{
	scanf("%d %d", &N, &M);

	for (int n = 1; n <= N; n++)
	{
		belt[n].front = belt[n].back = -1;
		belt[n].count = 0;
	}

	// M개의 물건 준비, n번 벨트에 추가 
	for (int m = 1; m <= M; m++)
	{
		int beltNum;

		scanf("%d", &beltNum);

		pushBack(beltNum, m);
	}
}

void moveAll(int m_src, int m_dst)
{
	BELT srcBelt = belt[m_src];
	if (srcBelt.count == 0)
	{
		printf("%d\n", belt[m_dst].count);
		return;
	}

	BELT dstBelt = belt[m_dst];
	int srcFrontBox = srcBelt.front;

	if (dstBelt.count == 0) // 이동할 벨트가 빈 경우
	{
		belt[m_dst] = srcBelt;
	}
	else
	{
		int srcLastBox = srcBelt.back;
		int dstFrontBox = dstBelt.front;

		box[srcLastBox].next = dstFrontBox;
		box[dstFrontBox].prev = srcLastBox;

		belt[m_dst].front = srcFrontBox;
		belt[m_dst].count += srcBelt.count;
	}

	// srcBelt 초기화
	belt[m_src].front = -1;
	belt[m_src].back = -1;
	belt[m_src].count = 0;

	printf("%d\n", belt[m_dst].count);
}

void changeFront(int m_src, int m_dst)
{
	int srcFrontBox = popFront(m_src);
	int dstFrontBox = popFront(m_dst);

	if (srcFrontBox == 0 && dstFrontBox == 0)
	{
		printf("0\n");
		return;
	}

	if (srcFrontBox != 0) pushFront(m_dst, srcFrontBox);
	if (dstFrontBox != 0) pushFront(m_src, dstFrontBox);

	printf("%d\n", belt[m_dst].count);
}

void splitBox(int m_src, int m_dst)
{
	int n = belt[m_src].count;

	int moveBox[MAX] = { 0 };
	for (int i = 0; i < n / 2; i++)
	{
		int srcFrontBox = popFront(m_src);
		moveBox[i] = srcFrontBox;
	}

	for (int i = (n / 2) - 1; i >= 0; i--)
		pushFront(m_dst, moveBox[i]);

	printf("%d\n", belt[m_dst].count);
}

void getPresent(int p_num)
{
	BOX pBox = box[p_num];
	int front = pBox.prev;
	int back = pBox.next;

	printf("%d\n", front + 2 * back);
}

void getBelt(int b_num)
{
	BELT b = belt[b_num];
	int front = b.front;
	int back = b.back;
	int count = b.count;

	printf("%d\n", front + 2 * back + 3 * count);
}

int main(void)
{
	scanf("%d", &Q);
	for (int q = 0; q < Q; q++)
	{
		scanf("%d", &COMMAND);

		if (COMMAND == FACTORY) input();
		else if (COMMAND == MOVE_ALL)
		{
			int m_src, m_dst;
			scanf("%d %d", &m_src, &m_dst);
			moveAll(m_src, m_dst);
		}
		else if (COMMAND == CHANGE_FRONT)
		{
			int m_src, m_dst;
			scanf("%d %d", &m_src, &m_dst);
			changeFront(m_src, m_dst);
		}
		else if (COMMAND == SPLIT)
		{
			int m_src, m_dst;
			scanf("%d %d", &m_src, &m_dst);
			splitBox(m_src, m_dst);
		}
		else if (COMMAND == GET_PRESENT)
		{
			int p_num;
			scanf("%d", &p_num);
			getPresent(p_num);
		}
		else if (COMMAND == GET_BELT)
		{
			int b_num;
			scanf("%d", &b_num);
			getBelt(b_num);
		}
	}

	return 0;
}