[C++] SWEA 2477 - 차량 정비소

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy&categoryId=AV6c6bgaIuoDFAXy&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2 

SW Expert Academy

<풀이>

1. 고객정보와 창구정보를 입력받고, 주어진 시뮬레이션을 돌린다.

2. 지갑을 분실했을 가능성이 있는 고객들의 고객번호 합을 구해 출력한다.

 

<해법>

1. 시뮬레이션 문제

=> 시뮬레이션 문제는 조건에 맞는 정확한 구현이 가장 중요합니다. 저는 코드를 짜기 전에 사용될 자료구조와, 조건에 맞는 구현 방법을 미리 생각합니다.

 

(1) 자료구조

저는 위와같이 초기 자료구조를 구상하였습니다.

 

(2) 조건에 맞는 구현방법

① (접수창구) 여러 고객이 기다리고 있는 경우 고객번호가 낮은 순서대로 우선 접수한다.

: 초기 고객 정보입력받는 큐에 고객번호가 낮은 순서대로 들어가있으므로, 접수창구줄 큐에도 고객번호가 낮은 순서대로 들어가게 된다. 따라서, 큐의 앞부분 부터 차례대로 접수 시킵니다.

 

② (접수창구) 빈 창구가 여러 곳인 경우 접수 창구번호가 작은 곳으로 간다.

: 접수 창구 배열을 앞부분부터 탐색하면서, 빈 창구일 경우 고객을 넣습니다.

 

③ (정비 창구) 먼저 기다리는 고객이 우선한다.

: 정비 창구 줄이 큐 이므로 만족합니다.

 

④ (정비 창구) 두 명 이상의 고객들이 접수 창구에서 동시에 접수를 완료하고 정비 창구로 이동한 경우, 이용했던 접수 창구번호가 작은 고객이 우선한다.

: 접수 창구 배열을 앞부분부터 탐색하면서 완료된 고객을 큐에 넣습니다.

 

⑤ (정비 창구) 빈 창구가 여러 곳인 경우 정비 창구번호가 작은 곳으로 간다.

: 정비 창구 배열을 앞부분부터 탐색하면서, 빈 창구일 경우 고객을 넣습니다.

 

⑥ 고객이 차량 정비소에 도착하여 접수 창구로 가는 시간 또는 접수 창구에서 정비 창구로 이동하는 시간은 무시할 수 있다. 즉, 이동 시간은 0이다.

: 동시에 이동한다는 뜻입니다. 하지만, 코드는 순차적으로 진행되기 때문에 교묘하게 동시처럼 보이게 해야합니다. 해결방법은 각 창구에서 완료된 사람을 먼저 빼낸 후에, 줄에 있는 사람을 창구에 배치합니다.

 

#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct customer {
    int index;
    int arriveTime;
    int timer;
    int a;
    int b;
};
 
struct desk {
    customer c;
    int time;
    bool isWorking;
};
 
int N, M, K, A, B;
desk aDesk[10];         //receptionDesk
desk bDesk[10];         //repairDesk
queue<customer> start;  //처음 입력받은 고객 명단
queue<customer> aLine;  //receptionDesk를 기다리는 줄
queue<customer> bLine;  //repairDesk를 기다리는 줄
int answer;
 
bool isWalletCustomer(customer c) {
    return (c.a == A && c.b == B) ? true : false;
}
 
void simulation() {
 
    int clock = 0;
    int finishCustomerNum = 0;
 
    while (true) {
 
        //시뮬레이션 종료조건
        if (finishCustomerNum == K) break;
 
        //start -> aLine
        while (!start.empty()) {
            customer c = start.front();
            if (c.arriveTime == clock) {
                aLine.push(c);
                start.pop();
            }
            else break;
        }
 
        //aDesk 고객 처리
        for (int i = 1; i <= N; i++) {
            //i번 창구에 고객이 있는 경우
            if (aDesk[i].isWorking) {
                //고객처리 완료했을 경우
                if (aDesk[i].c.timer == aDesk[i].time) {
                    aDesk[i].isWorking = false;
 
                    customer c = aDesk[i].c;
                    c.timer = 0;
                    bLine.push(c);
                }
                else {
                    aDesk[i].c.timer++;
                }
            }
        }
 
        //aLine -> aDesk
        for (int i = 1; i <= N; i++) {
            if (aLine.empty()) break;
            if (!aDesk[i].isWorking) {
                customer c = aLine.front();
                aLine.pop();
 
                c.a = i;
                c.timer++;
 
                aDesk[i].c = c;
                aDesk[i].isWorking = true;
            }
        }
 
        //bDesk 고객 처리
        for (int i = 1; i <= M; i++) {
            //i번 창구에 고객이 있는 경우
            if (bDesk[i].isWorking) {
                //고객처리 완료했을 경우
                if (bDesk[i].c.timer == bDesk[i].time) {
                    bDesk[i].isWorking = false;
                    customer c = bDesk[i].c;      
                    //지갑 분실 고객일 경우
                    if (isWalletCustomer(c)) {
                        if (answer == -1) answer = 0;
                        answer += c.index;
                    }
                    finishCustomerNum++;
                }
                else {
                    bDesk[i].c.timer++;
                }
            }
        }
 
        //bLine -> bDesk
        for (int i = 1; i <= M; i++) {
            if (bLine.empty()) break;
            if (!bDesk[i].isWorking) {
                customer c = bLine.front();
                bLine.pop();
 
                c.b = i;
                c.timer++;
 
                bDesk[i].c = c;
                bDesk[i].isWorking = true;
            }
        }
 
        clock++;
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, M = 0, K = 0, A = 0, B = 0;
        memset(aDesk, 0, sizeof(aDesk));
        memset(bDesk, 0, sizeof(bDesk));
        while (!start.empty()) start.pop();
        while (!aLine.empty()) aLine.pop();
        while (!bLine.empty()) bLine.pop();
        answer = -1;
 
        //입력
        cin >> N >> M >> K >> A >> B;
        for (int i = 1; i <= N; i++) {
            cin >> aDesk[i].time;
        }
        for (int i = 1; i <= M; i++) {
            cin >> bDesk[i].time;
        }
        for (int i = 1; i <= K; i++) {
            int arriveTime = 0;
            cin >> arriveTime;
            customer c = { i, arriveTime };
            start.push(c);
        }
 
        //해법
        simulation();
        
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

시뮬레이션에 대해 알아볼 수 있는 문제였습니다.