[코드트리] 산타의 선물 공장 2 (삼성 SW 역량테스트 2022 하반기 오후 2번, 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;
}