문제 출처
- https://www.swexpertacademy.com
난이도
- 하 – 중 – (상) – 최상 – 풀지 못함
문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)
- 정비소에서 차량을 고치기 위해서는 접수 후 정비가 가능하다. 접수와 정비 창구가 여러 개씩 주어지고, 각 창구의 접수 시간 및 정비 시간이 다를 때, 특정 창구를 이용한 사람을 찾는 문제이다.
- SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 상세히 문제를 설명하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.
후기
- 미생물 격리 문제와 비슷한 방식으로 문제를 해결하였다. 매시간 접수와 정비를 하는 사람의 위치를 파악하고, 접수나 정비가 완료되면 이동시키면서 창구 번호를 저장하는 방식을 사용했다.
- 개인적으로 미생물 격리보다 어렵다고 판단했던 부분은 접수창구와 정비창구 사이에 Stack을 사용해서 문제를 해결했기 때문이다. 특히 단순 Stack이 아니라 Stack을 Sorting 하면서 유지해야 하는 부분이 조금 까다롭다고 생각했다. 그리고 문제에서 Stack을 Sorting 하는 방식 설명을 잘못 읽어서 문제를 해결하는데 많은 시간을 허비했다. 항상 문제를 너무 빨리 읽고 넘어가는 경향이 있어서 조심할 필요가 있다.
코드
- 매 시간 접수/정비 창구 사람을 계산하는 코드
- 실행 시간: 7ms (제일 빠른 코드 대비 7배(1ms) 느림)
#include <stdio.h>
#define MAXSIZE 11
#define MAXPEOPLE 1002
//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable:4996)
int numCheck;
int numRepair;
int numPeople;
int numA, numB;
int checkTime[MAXSIZE];
int curCheck[MAXSIZE][2];
int repairTime[MAXSIZE];
int curRepair[MAXSIZE][2];
int finalResult[MAXPEOPLE][2];
int arrivalTime[MAXPEOPLE];
int tPtr;
int waitingPeople[MAXPEOPLE][3];
int sPtr;
int ePtr;
//MK: 접수 후 정비 창구로 이동하는 부분을 구현하기 위한 Stack 구현
void insertStack(int id, int time, int deskId) {
waitingPeople[ePtr][0] = id;
waitingPeople[ePtr][1] = time;
waitingPeople[ePtr][2] = deskId;
ePtr++;
}
//MK: 동일한 시간의 경우 정비 창구 번호에 따라 Sorting해야함
//MK: 개인적으로 이부분에서 에러가 발생하여 해결하는데 오랜 시간이 걸림
void popStack(int *retId) {
int ret = sPtr;
int id = waitingPeople[ret][0];
int cTime = waitingPeople[ret][1];
int deskId = waitingPeople[ret][2];
int i = ret + 1;
while (waitingPeople[i][1] == cTime) {
if (waitingPeople[i][2] < deskId) {
ret = i;
id = waitingPeople[i][0];
}
i++;
}
if (ret != sPtr) {
int tmpId = waitingPeople[sPtr][0];
int tmpTime = waitingPeople[sPtr][1];
waitingPeople[sPtr][0] = waitingPeople[ret][0];
waitingPeople[sPtr][1] = waitingPeople[ret][1];
waitingPeople[ret][0] = tmpId;
waitingPeople[ret][1] = tmpTime;
}
*retId = waitingPeople[sPtr][0];
waitingPeople[sPtr][0] = -1;
sPtr++;
return;
}
//MK: History 저장하기 위해 초기화 진행
void init() {
sPtr = 0;
ePtr = 0;
tPtr = 1;
for (int i = 0; i < MAXSIZE; i++) {
curCheck[i][0] = -1;
curCheck[i][1] = -1;
curRepair[i][0] = -1;
curRepair[i][1] = -1;
}
for (int i = 1; i <= numPeople; i++) {
waitingPeople[i][0] = -1;
waitingPeople[i][1] = -1;
}
}
//MK: 매 시간 접수/정비 창구의 사람을 체크하기 위한 코드
int finishedTime() {
int clock = 0;
int finished = 0;
int ret = 0;
while (finished < numPeople) {
for (int i = 1; i <= numCheck; i++) {
if (curCheck[i][0] != -1) {
curCheck[i][1]--;
if (curCheck[i][1] == 0) {
finalResult[curCheck[i][0]][0] = i;
insertStack(curCheck[i][0], clock, i);
curCheck[i][0] = -1;
}
}
if (curCheck[i][0] == -1 && arrivalTime[tPtr] <= clock && tPtr <= numPeople){
curCheck[i][0] = tPtr;
curCheck[i][1] = checkTime[i];
tPtr++;
}
}
for (int i = 1; i <= numRepair; i++) {
if (curRepair[i][0] != -1) {
curRepair[i][1]--;
if (curRepair[i][1] == 0) {
finished++;
finalResult[curRepair[i][0]][1] = i;
if (finalResult[curRepair[i][0]][0] == numA && i == numB) {
ret += curRepair[i][0];
}
curRepair[i][0] = -1;
}
}
if (curRepair[i][0] == -1) {
int id;
if (ePtr - sPtr > 0) {
popStack(&id);
curRepair[i][0] = id;
curRepair[i][1] = repairTime[i];
}
}
}
clock++;
}
//MK: 처음에 마지막에 이용한 사람을 찾기 위해 구현을 하였음. 수정하여 정비가 마무리 될때 체크하도록 변경함
//MK: 이 부분에서 대략 1ms 정도의 성능 손해가 발생
/*int ret = 0;
for (int i = 1; i <= numPeople; i++) {
if (finalResult[i][0] == numA && finalResult[i][1] == numB) {
ret += i;
}
}*/
if (ret == 0) {
return -1;
}
return ret;
}
int main(void)
{
int testCase;
freopen("input.txt", "r", stdin);
setbuf(stdout, NULL);
scanf("%d", &testCase);
for (int m = 1; m <= testCase; m++)
{
scanf("%d %d %d %d %d", &numCheck, &numRepair, &numPeople, &numA, &numB);
init();
for (int i = 1; i <= numCheck; i++) {
scanf("%d", &checkTime[i]);
}
for (int i = 1; i <= numRepair; i++) {
scanf("%d", &repairTime[i]);
}
for (int i = 1; i <= numPeople; i++) {
scanf("%d", &arrivalTime[i]);
}
printf("#%d %d\n", m, finishedTime());
}
return 0;
}