알고리즘/[ADV] 삼성 SW 역량 테스트 A형
[코드트리] 산타의 선물 공장 (삼성 SW 역량테스트 2022 하반기 오전 2번, B형)
피로물든딸기
2024. 7. 13. 15:40
반응형
2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,
A형 1문제 + B형 문제 1문제가 출제됩니다.
참고
- 더블 링크드 리스트 구현 (Double Linked List Tail ver)
https://www.codetree.ai/training-field/frequent-problems/problems/santa-gift-factory
문제를 요약하면 다음과 같다.
공장 설립
- 입력 값을 처리한다.
ID의 범위가 1 ≤ ID ≤ 1,000,000,000이기 때문에,
ID가 입력되는 순서(index)를 unordered_map에 저장한다.
물건 하차
- 벨트 앞의 물건 중 주어진 무게 이하의 상자 합을 저장하고, 벨트에서 삭제한다.
- 주어진 무게보다 큰 경우는 뒤로 보낸다.
더블 링크드 리스트를 이용하면, 벨트의 가장 앞에 있는 상자를 뒤로 보낼 수 있다.
물건 제거
- 벨트에서 물건을 제거하고, 제거된 경우 상자를 한 칸씩 당긴다.
unordere_map과 더블 링크드 리스트를 이용하면 제거된 상자를 찾아서 링크드 리스트에서 삭제할 수 있다.
물건 확인
- 물건을 확인하고, 확인할 물건이 있는 경우, 물건을 포함한 상자와 그 뒤의 상자도 앞으로 당긴다.
unordere_map과 더블 링크드 리스트를 이용하면 물건을 찾은 후, 한 번에 옮길 수 있다.
벨트 고장
- 벨트에 있는 상자를 통째로 옮긴다.
더블 링크드 리스트를 이용하면 물건을 한 번에 옮길 수 있다.
Hash Table vs unordered_map
해시 테이블의 직접 구현은 링크를 참고하자.
여기서는 C++의 unordered map을 사용한다.
만약 주어진 선물의 ID 범위가 작다면 (ex. 1,000,000), 다음과 같이 배열에 무게를 저장할 수 있다.
#include <stdio.h>
int arr[1000000 + 5];
int main(void)
{
// ID 가 1 ~ 1000000 라면
int id1 = 1000000;
arr[id1] = 5; // 무게 저장
return 0;
}
하지만 위 문제는 범위가 1 ≤ ID ≤ 1,000,000,000 이기 때문에 배열 a[1,000,000,000]은 메모리를 초과하게 된다.
따라서 unordered_map을 사용해서 ID를 관리한다.
unordered_map의 사용방법은 다음과 같다.
clear 메서드를 이용해 unordered_map을 초기화한다.
그리고 값을 저장하고 불러오는 방법이 배열과 같은 것을 알 수 있다.
#include <stdio.h>
#include <unordered_map>
using namespace std;
// int arr[1000000 + 5];
unordered_map<int, int> hashTable;
int main(void)
{
hashTable.clear();
// ID 가 1 ~ 100,000,000 인 경우
int id1 = 100000000;
hashTable[id1] = 5;
printf("id1 : %d, value = %d\n", id1, hashTable[id1]);
int id2 = 100000001;
hashTable[id2] = -5;
printf("id2 : %d, value = %d\n", id2, hashTable[id2]);
return 0;
}
hashTable[id2] = -5를 주석 처리 할 경우, hashTable에 id2를 저장하지 않아도, 호출하는 순간에 0이 저장된다.
// unordered map에 저장하지 않는 id
int id2 = 100000001;
// hashTable[id2] = -5;
printf("id2 : %d, value = %d\n", id2, hashTable[id2]);
따라서 값의 존재를 확인하기 위해서는 count를 이용해야 한다.
int id2 = 100000001;
// hashTable[id2] = -5;
// printf("id2 : %d, value = %d\n", id2, hashTable[id2]);
printf("check exist %d, %d\n", hashTable.count(id1), hashTable.count(id2));
주의 : printf에서 hastTable[id2] 값을 확인하고, count를 호출하면 1이 나오게 된다.
printf("id2 : %d, value = %d\n", id2, hashTable[id2]);
printf("check exist id1 : %d, id2 : %d\n", hashTable.count(id1), hashTable.count(id2));
실제 구현에서는 ID를 입력 순서의 index에 저장하고, 해당 index를 이용해 무게에 접근한다.
#include <stdio.h>
#include <unordered_map>
using namespace std;
// int arr[1000000 + 5];
unordered_map<int, int> hashTable;
int main(void)
{
hashTable.clear();
// ID 가 1 ~ 100,000,000 인 경우
int id1 = 100000000;
hashTable[id1] = 5;
printf("id1 : %d, value = %d\n", id1, hashTable[id1]);
int id2 = 100000001;
// hashTable[id2] = -5;
// printf("id2 : %d, value = %d\n", id2, hashTable[id2]);
printf("check exist id1 : %d, id2 : %d\n", hashTable.count(id1), hashTable.count(id2));
return 0;
}
| clear() | unordered_map을 초기화 한다. |
| count() | 존재하는 값이라면 1을, 없다면 0을 return한다. |
더블 링크드 리스트 구현
포인터를 이용한 구현은 링크를 참고하자.
여기서는 포인터 없이 배열에 index를 관리하는 방식으로 더블 링크드 리스트를 구현하였다.
구현 방법은 아래 설명을 참고하자.
구현
main은 다음과 같다.
입력(COMMAND)에 대해 공장 설립, 물건 하차, 물건 제거, 물건 확인, 벨트 고장을 실행한다.
#define FACTORY (100)
#define UNLOAD (200)
#define DELETE (300)
#define CHECK (400)
#define BROKEN (500)
#define UNLOAD_BOX (600) // 이름 변경
#define BROKEN_BELT (700)
#define EMPTY_BELT (-1)
#define CHECK_DELETE (-2)
...
int main(void)
{
scanf("%d", &Q);
for (int q = 0; q < Q; q++)
{
scanf("%d", &COMMAND);
if (COMMAND == FACTORY) input();
else if (COMMAND == UNLOAD)
{
int w_max;
scanf("%d", &w_max);
unload(w_max);
}
else if (COMMAND == DELETE)
{
int r_id;
scanf("%d", &r_id);
deleteBox(r_id);
}
else if (COMMAND == CHECK)
{
int f_id;
scanf("%d", &f_id);
checkBox(f_id);
}
else if (COMMAND == BROKEN)
{
int b_num;
scanf("%d", &b_num);
brokenBelt(b_num);
}
}
return 0;
}공장 설립
BOXINFO에는 상자의 무게와 하차 여부(삭제 여부)를 관리한다.
typedef struct st1
{
int weight;
int unload;
}BOXINFO;
BOXINFO BOX[MAX];
boxMap은 상자의 ID와 들어오는 순서를 mapping하고, betlMap은 현재 상자가 어느 벨트에 있는지 저장한다.
unordered_map<int, int> boxMap;
unordered_map<int, int> beltMap;
checkBelt는 고장난 벨트를 확인한다.
int checkBelt[10 + 5];
더블 링크드 리스트를 만들기 위한 구조체 BELT를 선언한다.
prev가 상자의 앞에 있는 index가 되고, next는 상자 뒤의 index가 된다.
typedef struct st2
{
int id;
int weight;
int unload;
int prev;
int next;
}BELT;
BOXINFO BOX[MAX];
BELT HEAD[10 + 5];
BELT TAIL[10 + 5];
BELT NODE[MAX];
int nIdx;
ID와 무게(W)는 들어오는 순서대로 입력을 받는다.
for (int n = 0; n < N; n++) scanf("%d", &ID[n]);
for (int n = 0; n < N; n++) scanf("%d", &W[n]);
BOX ID와 box가 들어온 순서를 mapping한다.
for (int n = 0; n < N; n++)
{
boxMap[ID[n]] = n;
BOX[n].unload = 0;
BOX[n].weight = W[n];
}
상자는 들어온 순서대로 벨트에 할당되므로, N / M 칸씩 나눠서 1번 벨트부터 링크드 리스트를 만든다.
TAIL과 HEAD는 index를 -1로 설정하였다.
int index = 0;
int count = N / M;
for (int m = 1; m <= M; m++)
{
HEAD[m].prev = -1;
TAIL[m].next = -1;
int startIndex = index;
for (int i = 0; i < count; i++)
{
NODE[nIdx].id = ID[index];
NODE[nIdx].weight = W[index];
NODE[nIdx].unload = 0;
NODE[nIdx].prev = index - 1;
NODE[nIdx++].next = index + 1;
beltMap[ID[index++]] = m; // box의 belt 위치
}
NODE[startIndex].prev = -1;
NODE[nIdx - 1].next = -1; // 마지막 node는 Tail로 설정
HEAD[m].next = startIndex;
TAIL[m].prev = index - 1;
}
전체 코드는 다음과 같다.
void input()
{
scanf("%d %d", &N, &M);
boxMap.clear();
beltMap.clear();
for (int m = 1; m <= M; m++) checkBelt[m] = 0;
for (int n = 0; n < N; n++) scanf("%d", &ID[n]);
for (int n = 0; n < N; n++) scanf("%d", &W[n]);
for (int n = 0; n < N; n++)
{
boxMap[ID[n]] = n;
BOX[n].unload = 0;
BOX[n].weight = W[n];
}
nIdx = 0;
int index = 0;
int count = N / M;
for (int m = 1; m <= M; m++)
{
HEAD[m].prev = -1;
TAIL[m].next = -1;
int startIndex = index;
for (int i = 0; i < count; i++)
{
NODE[nIdx].id = ID[index];
NODE[nIdx].weight = W[index];
NODE[nIdx].unload = 0;
NODE[nIdx].prev = index - 1;
NODE[nIdx++].next = index + 1;
beltMap[ID[index++]] = m; // box의 belt 위치
}
NODE[startIndex].prev = -1;
NODE[nIdx - 1].next = -1; // 마지막 node는 Tail로 설정
HEAD[m].next = startIndex;
TAIL[m].prev = index - 1;
}
}물건 하차
모든 벨트에 가장 앞에 있는 상자를 확인한다.
상자의 합은 int 범위를 넘어가기 때문에 long long 타입으로 누적해야 한다.
typedef long long ll;
...
ll totalWeight = 0;
for (int m = 1; m <= M; m++) { ... }
HEAD의 next가 가장 앞의 상자가 된다.
-1이 나온다는 것은 HEAD가 TAIL을 가르키는 것이므로, 벨트가 비어 있다는 뜻이 된다.
고장난 벨트도 continue로 넘어간다.
int firstBoxIndex = HEAD[m].next;
if (firstBoxIndex == -1 || checkBelt[m] == BROKEN_BELT) continue;
가장 앞의 상자 다음 상자가 HEAD를 가르켜야 하므로, 다음 상자의 index를 구한다.
int frontNextIndex = NODE[firstBoxIndex].next;
HEAD의 next를 frontNextIndex로 설정해서 가장 앞의 상자로 만든다.
frontNextIndex가 -1이란 것은 벨트에 상자가 하나 밖에 없다는 것을 의미해서 예외처리 한다.
그렇지 않다면 prev를 HEAD를 향하게 한다.
HEAD[m].next = frontNextIndex;
if (frontNextIndex == -1) TAIL[m].prev = -1;
else NODE[frontNextIndex].prev = -1;
상자가 w_max보다 무게가 작다면 누적하고, unload에 UNLOAD 표시를 한다.
그렇지 않은 경우, TAIL의 바로 앞 (TAIL[m].prev)에 상자를 추가한다.
int weight = NODE[firstBoxIndex].weight;
if (weight <= w_max)
{
NODE[firstBoxIndex].unload = UNLOAD;
totalWeight += weight;
}
else
{
int lastBoxIndex = TAIL[m].prev;
if (lastBoxIndex == -1) // 상자가 1개인 경우.
{
HEAD[m].next = firstBoxIndex;
NODE[firstBoxIndex].prev = -1;
NODE[firstBoxIndex].next = -1;
TAIL[m].prev = firstBoxIndex;
}
else
{
NODE[lastBoxIndex].next = firstBoxIndex;
NODE[firstBoxIndex].prev = lastBoxIndex;
NODE[firstBoxIndex].next = -1;
TAIL[m].prev = firstBoxIndex;
}
}
전체 코드는 다음과 같다.
void unload(int w_max)
{
ll totalWeight = 0;
for (int m = 1; m <= M; m++)
{
int firstBoxIndex = HEAD[m].next;
if (firstBoxIndex == -1 || checkBelt[m] == BROKEN_BELT) continue;
int frontNextIndex = NODE[firstBoxIndex].next;
HEAD[m].next = frontNextIndex;
if (frontNextIndex == -1) TAIL[m].prev = -1;
else NODE[frontNextIndex].prev = -1;
int weight = NODE[firstBoxIndex].weight;
if (weight <= w_max)
{
NODE[firstBoxIndex].unload = UNLOAD;
totalWeight += weight;
}
else
{
int lastBoxIndex = TAIL[m].prev;
if (lastBoxIndex == -1) // 상자가 1개인 경우.
{
HEAD[m].next = firstBoxIndex;
NODE[firstBoxIndex].prev = -1;
NODE[firstBoxIndex].next = -1;
TAIL[m].prev = firstBoxIndex;
}
else
{
NODE[lastBoxIndex].next = firstBoxIndex;
NODE[firstBoxIndex].prev = lastBoxIndex;
NODE[firstBoxIndex].next = -1;
TAIL[m].prev = firstBoxIndex;
}
}
}
printf("%lld\n", totalWeight);
}물건 제거
주어진 ID에 대해 count를 이용하여 존재하지 않는 입력인 경우와, 이미 삭제된 경우에 대한 처리를 한다.
if (boxMap.count(r_id) == 0)
{
printf("%d\n", -1);
return;
}
int boxIndex = boxMap[r_id];
if (NODE[boxIndex].unload == UNLOAD)
{
printf("%d\n", -1);
return;
}
상자가 존재하는 경우,
1. 해당 ID로 belt 번호를 찾는다.
2. 상자의 앞과 상자의 뒤 상자를 찾는다.
3. 상자의 앞과 상자의 뒤를 연결한다. (앞, 뒤가 없는 경우 예외 처리)
4. 상자에 UNLOAD라고 표기하고, ID를 출력한다.
int beltNum = beltMap[r_id];
int prevBoxIndex = NODE[boxIndex].prev;
int nextBoxIndex = NODE[boxIndex].next;
if (prevBoxIndex != -1) NODE[prevBoxIndex].next = nextBoxIndex;
else HEAD[beltNum].next = nextBoxIndex;
if (nextBoxIndex != -1) NODE[nextBoxIndex].prev = prevBoxIndex;
else TAIL[beltNum].prev = prevBoxIndex;
NODE[boxIndex].unload = UNLOAD;
printf("%d\n", r_id);
전체 코드는 다음과 같다.
void deleteBox(int r_id)
{
if (boxMap.count(r_id) == 0)
{
printf("%d\n", -1);
return;
}
int boxIndex = boxMap[r_id];
if (NODE[boxIndex].unload == UNLOAD)
{
printf("%d\n", -1);
return;
}
int beltNum = beltMap[r_id];
int prevBoxIndex = NODE[boxIndex].prev;
int nextBoxIndex = NODE[boxIndex].next;
if (prevBoxIndex != -1) NODE[prevBoxIndex].next = nextBoxIndex;
else HEAD[beltNum].next = nextBoxIndex;
if (nextBoxIndex != -1) NODE[nextBoxIndex].prev = prevBoxIndex;
else TAIL[beltNum].prev = prevBoxIndex;
NODE[boxIndex].unload = UNLOAD;
printf("%d\n", r_id);
}물건 확인
입력받지 않은 상자 또는 이미 하차된 상자에 대한 처리를 한다.
if (boxMap.count(f_id) == 0)
{
printf("%d\n", -1);
return;
}
int boxIndex = boxMap[f_id];
if (NODE[boxIndex].unload == UNLOAD)
{
printf("%d\n", -1);
return;
}
벨트 번호를 찾고, 해당 상자의 바로 앞 상자를 찾는다.
앞 상자가 -1 (HEAD)인 경우는 상자를 옮길 필요가 없으므로 벨트 번호를 출력하고 종료한다.
int beltNum = beltMap[f_id];
int prevBoxIndex = NODE[boxIndex].prev; // 선택된 상자의 바로 앞 상자
if (prevBoxIndex == -1) // 가장 앞에 있는 경우는 옮길 필요가 없다.
{
printf("%d\n", beltNum);
return;
}
바로 앞의 상자가 있는 경우 예시를 보자.
1, 2, 3, 4, 5, 6, 7 상자에서 확인할 상자가 5라면,
바로 앞의 상자 = 4
첫 번째 상자 = 1
마지막 상자 = 7
5 확인 후 → 5, 6, 7, 1, 2, 3, 4 가 된다.
즉,
1) HEAD의 다음은 5를 가르켜야 하고
2) 5번 상자의 앞은 HEAD를 가르켜야 한다.
3) 첫 번째 상자의 앞은 마지막 상자를 가르키고
4) 바로 앞의 상자의 뒤는 TAIL을 가르켜야 한다.
5) 마지막 상자의 뒤는 첫 번째 상자를 가르키고,
6) TAIL은 바로 앞의 상자를 가르켜야 한다.
코드로 구현하면 다음과 같다.
int firstBoxIndex = HEAD[beltNum].next; // 가장 앞의 상자
int lastBoxIndex = TAIL[beltNum].prev; // 가장 뒤의 상자
HEAD[beltNum].next = boxIndex;
NODE[boxIndex].prev = -1;
NODE[firstBoxIndex].prev = lastBoxIndex;
NODE[prevBoxIndex].next = -1;
NODE[lastBoxIndex].next = firstBoxIndex;
TAIL[beltNum].prev = prevBoxIndex;
printf("%d\n", beltNum);
전체 코드는 다음과 같다.
void checkBox(int f_id)
{
if (boxMap.count(f_id) == 0)
{
printf("%d\n", -1);
return;
}
int boxIndex = boxMap[f_id];
if (NODE[boxIndex].unload == UNLOAD)
{
printf("%d\n", -1);
return;
}
int beltNum = beltMap[f_id];
int prevBoxIndex = NODE[boxIndex].prev; // 선택된 상자의 바로 앞 상자
if (prevBoxIndex == -1) // 가장 앞에 있는 경우는 옮길 필요가 없다.
{
printf("%d\n", beltNum);
return;
}
int firstBoxIndex = HEAD[beltNum].next; // 가장 앞의 상자
int lastBoxIndex = TAIL[beltNum].prev; // 가장 뒤의 상자
HEAD[beltNum].next = boxIndex;
NODE[boxIndex].prev = -1;
NODE[firstBoxIndex].prev = lastBoxIndex;
NODE[prevBoxIndex].next = -1;
NODE[lastBoxIndex].next = firstBoxIndex;
TAIL[beltNum].prev = prevBoxIndex;
printf("%d\n", beltNum);
}벨트 고장
이미 고장난 벨트에 대한 처리를 하고, 그렇지 않은 경우, checkBelt에 기록한다.
if (checkBelt[b_num] == BROKEN_BELT)
{
printf("%d\n", -1);
return;
}
checkBelt[b_num] = BROKEN_BELT;
고장난 벨트를 기준으로 오른쪽 벨트 중 고장나지 않은 벨트를 찾는다.
찾지 못하는 경우 1번 벨트부터 다시 찾는다.
int nextBeltNum = -1;
for (int m = b_num + 1; m <= M; m++)
{
if (checkBelt[m] == BROKEN_BELT) continue;
else
{
nextBeltNum = m;
break;
}
}
if (nextBeltNum == -1) // 고장난 벨트 오른쪽에 정상 벨트가 없는 경우
{
for (int m = 1; m < b_num; m++)
{
if (checkBelt[m] == BROKEN_BELT) continue;
else
{
nextBeltNum = m;
break;
}
}
}
고장난 벨트의 가장 앞 상자와 가장 뒤의 상자, 그리고 옮길 벨트의 가장 뒤의 상자의 index를 찾는다.
int brokenFirstBoxIndex = HEAD[b_num].next; // 고장난 벨트의 앞 상자
int brokenLastBoxIndex = TAIL[b_num].prev; // 고장난 벨트의 뒤 상자
int lastBoxIndex = TAIL[nextBeltNum].prev; // 옮길 벨트의 뒤 상자
고장난 벨트가 빈 경우는 아무것도 하지 않고 벨트 번호를 출력하고 종료한다.
if (brokenFirstBoxIndex == -1) // 고장난 벨트가 빈 경우
{
printf("%d\n", b_num);
return;
}
이제 벨트에 있는 상자를 통째로 옮긴다.
옮길 벨트가 빈 경우에는 HEAD와 TAIL만 연결하면 된다.
옮길 벨트에 상자가 있는 경우 가장 뒤의 상자에 연결한다.
// 벨트 변경
changeBelt(b_num, nextBeltNum);
if (lastBoxIndex == -1) // 옮길 벨트가 빈 경우
{
HEAD[nextBeltNum].next = brokenFirstBoxIndex;
TAIL[nextBeltNum].prev = brokenLastBoxIndex;
}
else
{
NODE[lastBoxIndex].next = brokenFirstBoxIndex;
NODE[brokenFirstBoxIndex].prev = lastBoxIndex;
NODE[brokenLastBoxIndex].next = -1;
TAIL[nextBeltNum].prev = brokenLastBoxIndex;
}
printf("%d\n", b_num);
전체 코드는 다음과 같다.
void brokenBelt(int b_num)
{
if (checkBelt[b_num] == BROKEN_BELT)
{
printf("%d\n", -1);
return;
}
checkBelt[b_num] = BROKEN_BELT;
int nextBeltNum = -1;
for (int m = b_num + 1; m <= M; m++)
{
if (checkBelt[m] == BROKEN_BELT) continue;
else
{
nextBeltNum = m;
break;
}
}
if (nextBeltNum == -1) // 고장난 벨트 오른쪽에 정상 벨트가 없는 경우
{
for (int m = 1; m < b_num; m++)
{
if (checkBelt[m] == BROKEN_BELT) continue;
else
{
nextBeltNum = m;
break;
}
}
}
int brokenFirstBoxIndex = HEAD[b_num].next; // 고장난 벨트의 앞 상자
int brokenLastBoxIndex = TAIL[b_num].prev; // 고장난 벨트의 뒤 상자
int lastBoxIndex = TAIL[nextBeltNum].prev; // 옮길 벨트의 뒤 상자
if (brokenFirstBoxIndex == -1) // 고장난 벨트가 빈 경우
{
printf("%d\n", b_num);
return;
}
// 벨트 변경
changeBelt(b_num, nextBeltNum);
if (lastBoxIndex == -1) // 옮길 벨트가 빈 경우
{
HEAD[nextBeltNum].next = brokenFirstBoxIndex;
TAIL[nextBeltNum].prev = brokenLastBoxIndex;
}
else
{
NODE[lastBoxIndex].next = brokenFirstBoxIndex;
NODE[brokenFirstBoxIndex].prev = lastBoxIndex;
NODE[brokenLastBoxIndex].next = -1;
TAIL[nextBeltNum].prev = brokenLastBoxIndex;
}
printf("%d\n", b_num);
}debug 함수를 만들어서 더블 링크드 리스트가 제대로 동작하는지 꼭 확인하자.
void printBelt(int beltNum)
{
int index = HEAD[beltNum].next;
printf("belt %d : ", beltNum);
while (1)
{
if (index == -1) break;
BELT tmp = NODE[index];
printf("(%d : %d), ", tmp.id, tmp.weight);
index = tmp.next;
}
printf("TAIL %d %d", NODE[TAIL[beltNum].prev].id, NODE[TAIL[beltNum].prev].weight);
putchar('\n');
}
void printAll()
{
for (int m = 1; m <= M; m++)
{
if (checkBelt[m] == BROKEN_BELT) continue;
printBelt(m);
}
putchar('\n');
}
전체 코드는 다음과 같다.
#include <stdio.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
#define MAX (200000 + 5000)
#define FACTORY (100)
#define UNLOAD (200)
#define DELETE (300)
#define CHECK (400)
#define BROKEN (500)
#define UNLOAD_BOX (600) // 이름 변경
#define BROKEN_BELT (700)
#define EMPTY_BELT (-1)
#define CHECK_DELETE (-2)
int T;
int Q, COMMAND, N, M;
int ID[MAX];
int W[MAX];
typedef struct st1
{
int weight;
int unload;
}BOXINFO;
typedef struct st2
{
int id;
int weight;
int unload;
int prev;
int next;
}BELT;
BOXINFO BOX[MAX];
BELT HEAD[10 + 5];
BELT TAIL[10 + 5];
BELT NODE[MAX];
int nIdx;
int checkBelt[10 + 5];
unordered_map<int, int> boxMap;
unordered_map<int, int> beltMap;
void printBelt(int beltNum)
{
int index = HEAD[beltNum].next;
printf("belt %d : ", beltNum);
while (1)
{
if (index == -1) break;
BELT tmp = NODE[index];
printf("(%d : %d), ", tmp.id, tmp.weight);
index = tmp.next;
}
printf("TAIL %d %d", NODE[TAIL[beltNum].prev].id, NODE[TAIL[beltNum].prev].weight);
putchar('\n');
}
void printAll()
{
for (int m = 1; m <= M; m++)
{
if (checkBelt[m] == BROKEN_BELT) continue;
printBelt(m);
}
putchar('\n');
}
void changeBelt(int beltNum, int changeNum)
{
int index = HEAD[beltNum].next;
while (1)
{
if (index == -1) break;
BELT tmp = NODE[index];
beltMap[tmp.id] = changeNum;
index = tmp.next;
}
}
void input()
{
scanf("%d %d", &N, &M);
boxMap.clear();
beltMap.clear();
for (int m = 1; m <= M; m++) checkBelt[m] = 0;
for (int n = 0; n < N; n++) scanf("%d", &ID[n]);
for (int n = 0; n < N; n++) scanf("%d", &W[n]);
for (int n = 0; n < N; n++)
{
boxMap[ID[n]] = n;
BOX[n].unload = 0;
BOX[n].weight = W[n];
}
nIdx = 0;
int index = 0;
int count = N / M;
for (int m = 1; m <= M; m++)
{
HEAD[m].prev = -1;
TAIL[m].next = -1;
int startIndex = index;
for (int i = 0; i < count; i++)
{
NODE[nIdx].id = ID[index];
NODE[nIdx].weight = W[index];
NODE[nIdx].unload = 0;
NODE[nIdx].prev = index - 1;
NODE[nIdx++].next = index + 1;
beltMap[ID[index++]] = m; // box의 belt 위치
}
NODE[startIndex].prev = -1;
NODE[nIdx - 1].next = -1; // 마지막 node는 Tail로 설정
HEAD[m].next = startIndex;
TAIL[m].prev = index - 1;
}
}
void unload(int w_max)
{
ll totalWeight = 0;
for (int m = 1; m <= M; m++)
{
int firstBoxIndex = HEAD[m].next;
if (firstBoxIndex == -1 || checkBelt[m] == BROKEN_BELT) continue;
int frontNextIndex = NODE[firstBoxIndex].next;
HEAD[m].next = frontNextIndex;
if (frontNextIndex == -1) TAIL[m].prev = -1;
else NODE[frontNextIndex].prev = -1;
int weight = NODE[firstBoxIndex].weight;
if (weight <= w_max)
{
NODE[firstBoxIndex].unload = UNLOAD;
totalWeight += weight;
}
else
{
int lastBoxIndex = TAIL[m].prev;
if (lastBoxIndex == -1) // 상자가 1개인 경우.
{
HEAD[m].next = firstBoxIndex;
NODE[firstBoxIndex].prev = -1;
NODE[firstBoxIndex].next = -1;
TAIL[m].prev = firstBoxIndex;
}
else
{
NODE[lastBoxIndex].next = firstBoxIndex;
NODE[firstBoxIndex].prev = lastBoxIndex;
NODE[firstBoxIndex].next = -1;
TAIL[m].prev = firstBoxIndex;
}
}
}
printf("%lld\n", totalWeight);
}
void deleteBox(int r_id)
{
if (boxMap.count(r_id) == 0)
{
printf("%d\n", -1);
return;
}
int boxIndex = boxMap[r_id];
if (NODE[boxIndex].unload == UNLOAD)
{
printf("%d\n", -1);
return;
}
int beltNum = beltMap[r_id];
int prevBoxIndex = NODE[boxIndex].prev;
int nextBoxIndex = NODE[boxIndex].next;
if (prevBoxIndex != -1) NODE[prevBoxIndex].next = nextBoxIndex;
else HEAD[beltNum].next = nextBoxIndex;
if (nextBoxIndex != -1) NODE[nextBoxIndex].prev = prevBoxIndex;
else TAIL[beltNum].prev = prevBoxIndex;
NODE[boxIndex].unload = UNLOAD;
printf("%d\n", r_id);
}
void checkBox(int f_id)
{
if (boxMap.count(f_id) == 0)
{
printf("%d\n", -1);
return;
}
int boxIndex = boxMap[f_id];
if (NODE[boxIndex].unload == UNLOAD)
{
printf("%d\n", -1);
return;
}
int beltNum = beltMap[f_id];
int prevBoxIndex = NODE[boxIndex].prev; // 선택된 상자의 바로 앞 상자
if (prevBoxIndex == -1) // 가장 앞에 있는 경우는 옮길 필요가 없다.
{
printf("%d\n", beltNum);
return;
}
int firstBoxIndex = HEAD[beltNum].next; // 가장 앞의 상자
int lastBoxIndex = TAIL[beltNum].prev; // 가장 뒤의 상자
HEAD[beltNum].next = boxIndex;
NODE[boxIndex].prev = -1;
NODE[firstBoxIndex].prev = lastBoxIndex;
NODE[prevBoxIndex].next = -1;
NODE[lastBoxIndex].next = firstBoxIndex;
TAIL[beltNum].prev = prevBoxIndex;
printf("%d\n", beltNum);
}
void brokenBelt(int b_num)
{
if (checkBelt[b_num] == BROKEN_BELT)
{
printf("%d\n", -1);
return;
}
checkBelt[b_num] = BROKEN_BELT;
int nextBeltNum = -1;
for (int m = b_num + 1; m <= M; m++)
{
if (checkBelt[m] == BROKEN_BELT) continue;
else
{
nextBeltNum = m;
break;
}
}
if (nextBeltNum == -1) // 고장난 벨트 오른쪽에 정상 벨트가 없는 경우
{
for (int m = 1; m < b_num; m++)
{
if (checkBelt[m] == BROKEN_BELT) continue;
else
{
nextBeltNum = m;
break;
}
}
}
int brokenFirstBoxIndex = HEAD[b_num].next; // 고장난 벨트의 앞 상자
int brokenLastBoxIndex = TAIL[b_num].prev; // 고장난 벨트의 뒤 상자
int lastBoxIndex = TAIL[nextBeltNum].prev; // 옮길 벨트의 뒤 상자
if (brokenFirstBoxIndex == -1) // 고장난 벨트가 빈 경우
{
printf("%d\n", b_num);
return;
}
// 벨트 변경
changeBelt(b_num, nextBeltNum);
if (lastBoxIndex == -1) // 옮길 벨트가 빈 경우
{
HEAD[nextBeltNum].next = brokenFirstBoxIndex;
TAIL[nextBeltNum].prev = brokenLastBoxIndex;
}
else
{
NODE[lastBoxIndex].next = brokenFirstBoxIndex;
NODE[brokenFirstBoxIndex].prev = lastBoxIndex;
NODE[brokenLastBoxIndex].next = -1;
TAIL[nextBeltNum].prev = brokenLastBoxIndex;
}
printf("%d\n", b_num);
}
int main(void)
{
scanf("%d", &Q);
for (int q = 0; q < Q; q++)
{
scanf("%d", &COMMAND);
if (COMMAND == FACTORY) input();
else if (COMMAND == UNLOAD)
{
int w_max;
scanf("%d", &w_max);
unload(w_max);
}
else if (COMMAND == DELETE)
{
int r_id;
scanf("%d", &r_id);
deleteBox(r_id);
}
else if (COMMAND == CHECK)
{
int f_id;
scanf("%d", &f_id);
checkBox(f_id);
}
else if (COMMAND == BROKEN)
{
int b_num;
scanf("%d", &b_num);
brokenBelt(b_num);
}
}
return 0;
}반응형