[SWEA 2477] 차량 정비소

문제  : [모의 SW 역량테스트] - 차량 정비소

[문제 출처] : SW Expert Academy [모의 SW 역량테스트] - 차량 정비소

 

 

[문제풀이]

 

이 문제는 삼성 SW 모의 역량 테스트에서 많이 볼 수 있는 전형적인 시뮬레이션 문제이다

시뮬레이션 문제라고 하면은 대게 1초,  1시간 혹은 하루가 지나면서 달라지는 상황 등을 조건에 맞게 구현하는 문제이다

시뮬레이션 문제는 대게 비슷한 큰 틀을 갖는다 그렇기 때문에 여러 가지 비슷한 시뮬레이션 문제들을 풀다 보면 큰 틀은

다르지 않음을 알 수 있을 것이다 문제마다 처리해야 할 조건 혹은 구현에서 차이가 있을 뿐 큰 틀은 다르지 않다 그래서

여러 가지 상황의 문제들을 풀다 보면은 감을 잡을 수 있을 것이다!!

 

BOJ에서 많은 시뮬레이션 문제들을 풀어 보았지만 SWEA에서 접한 문제들은 대게 조건이 복잡하고 구현이 조금은 까다 롭다

하지만 SWEA에서는 대게 문제의 설명을 텍스트뿐만 아니라 그림으로서 예제 입력을 문제에서 요구하는 시간 단위로 나누어

갖가지의 상황을 그림으로 자세하게 묘사해준다.  즉 그림만 이해해도 문제의 절반을 풀었다고 볼 수 있는 셈이다!!

 

하지만 나의 경우는 달랐다.. 여러 가지 문제 등을 풀어 보았고 나름 자부했지만은  해당 문제를 풀면서 스트레스 아닌 스트레

수를 받았던 것 같다  후..  문제에 대한 이해는 친절한 그림설명으로 빠르게 이해할 수 있었다

 

(TMI)....

 

다시 본론으로 어떻게 문제를 해결해야 할지 살펴보자

 

1. 시뮬레이션 문제를 풀기 위한 큰 틀(반복문으로 시간의 흐름을 표현)을 설정해준다.

 

for (int time = 0;  time <= MAX ; ++time)  {  

	//  해당 조건들을 구현해준다
    
}

※ 주의 사항

제출을 여러 번 하면서 알게 된 점이기도 하다

time 최댓값을 점점 늘려서 테케 37PASS ---> 41PASS ---> ALL PASS를 할 수 있었다

시간을 최대 몇 초(?)까지 잡아야 하냐는 것이다

몇 초 후에 모든 고객들이 접수를 하고 차량 정비를 다 마치고 집에 돌아갈까?

물론 위와 같이 꼭 구현해 줄 필요는 없다..

모든 큐 와 창구가 비어있는지를 조건문으로 설정해 반복문을 탈출하면 그만 이기 때문이다

이는 최악의 경우를 생각해 보면 된다 

 

나름 최악의 경우를 생각해보자 ::))

 

[제약사항]을 살펴보면

(0 ≤ tk ≤ 1,000) 

(2 ≤ K ≤ 1,000) 임을 알 수 있다

 

그러니깐 1000초 후에 1000명의 인원이 몰려오는 경우로 볼 수 있지 않을까? 게다가 접수창구 1개 정비 창구 1개인 경우로

아! 각각의 처리시간도 가장 늦은 20초로 설정해서 말이다! 대략 1000 + 1000*20 이기 때문에 적당한 값으로 MAX 값을 

설정 해주자! 그냥 대략적으로 MAX = 21002로 설정하였다.

 

 

2. 여러 가지 상황을 생각해보기 전에 자료구조는 무엇을 써야 할지? 

 

다들 알겠지만 은행에 가면 번호표를 뽑는다 즉 오는 순서대로 , 시간 순서대로 우선순위를 부여하여 먼저 온 순번대로 먼저

처리를 받을 수 있어야 한다 이를 구현하기 위해서는 FIFO 타입의  큐를 이용하는 것이 좋을 것 같다.

물론 창구에 들어가기 전 대기하는 이들을 저장하기 위한 것이다.

접수창구 정비 창구의 경우 그냥 vector로 표현하였고 pair<int, int> 를 통해서 처리하고 있는

고객번호와 처리 시간을 저장하였다

 

queue<int> receptionWatingQ;        // 접수 창구로 가기전 대기실
queue<int> maintenanceWatingQ;      // 정비 창구로 가기전 대기실
vector<pair<int, int> > receptionCounter(n + 1);    // 접수 창구
vector<pair<int, int> > maintenanceCounter(m + 1);    // 정비 창구

 

 

3. 무엇부터 해결할지?

 

이 그림을 보면 풀이(?)에 가까운 답을 떠올릴 수 있다. 대기실에 있던 손님이 창구로 가기 위해서는 창구에 있는 

손님을 다음 단계(?)로 보내 주어야 한다. 물론 처리 시간을 다한 창구에 한에서 말이다

 

1.  접수창구           -->    차량 정비 대기실 

2.  차량 정비 창구  -->   집 (일을 마쳤으니 더 이상 있어봤자 의미 없다) 그냥 없애 준다

 

 

이제 대기실에 있는 인원들을 창구로 옮겨 보자!

 

1. 접수 대기실  --> 접수 창구

2. 정비 대기실  --> 정비 창구

 

물론 위에 2개는 1번과 2번 순서는 바꾸어도 상관은 없지만 창구에 있는 손님을 다음 단계로 보내주는 것이 우선이기 

때문에 대기실에서 창구로 가는 구현은 그 후의 위치에 구현을 해주어야 한다.

 

+ 추가적으로 

시뮬레이션 문제를 푸는 팁 중에 하나는(감히 팁을 언급하자면) 디버깅을 하는 코드를 생각하면서 코드를 구현하면

나중에 디버깅하기도 편하고 빠르게 코드를 수정해 나갈 수 있다 문제에 나와있는 간단한 예시 입력을 넣어 보면서 빠르게

 고쳐 나간다면 빠진 조건 혹은 생각하지 못한 조건을 찾아 정답에 가까운 코드를 빠르게 찾아 나갈 수 있을 것이라 생각된다

 

 

 

[소스 코드]

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 11;
int n, m, k, A, B;
int receptionTime[MAX], maintenanceTime[MAX], guestTime[1001];
vector<int> Ai, Bi;
int solve() {
    Ai.clear(), Bi.clear();
    int cnt = 1, ans = 0;
    queue<int> receptionWatingQ;
    queue<int> maintenanceWatingQ;
    vector<pair<int, int> > receptionCounter(n + 1);
    vector<pair<int, int> > maintenanceCounter(m + 1);
    for (int time = 0; time <= 20000 + 1002; ++time) {
         //cout << "time : " << time << "\n";
 
        // 차량 정비소에 도착 한 순서대로 'receptionWaingQ'에 넣어 준다.
        while (cnt != (k + 1) && guestTime[cnt] == time) {
            // cout << "Guest : " << cnt << '\n';
            receptionWatingQ.push(cnt);
            cnt++;
        }
        // 정비 창구 --> 집
        for (int i = 1; i <= m; i++) {
            if (maintenanceCounter[i].first == 0) continue;
            if (maintenanceCounter[i].second == maintenanceTime[i]) {
                maintenanceCounter[i] = make_pair(0, 0);
            }
        }
        // 접수 창구 --> 정비 대기실
        for (int i = 1; i <= n; i++) {
            if (receptionCounter[i].first == 0) continue;
            if (receptionCounter[i].second == receptionTime[i]) {
                maintenanceWatingQ.push(receptionCounter[i].first);
                receptionCounter[i] = make_pair(0, 0);
            }
        }
        // 접수 대기실 (큐) --> 접수 창구
        int idx = 1;
         //cout << "reception : " << '\n';
        while (idx != (n + 1) && !receptionWatingQ.empty()) {
            if (receptionCounter[idx].first != 0) {
                idx++;
                continue;
            }
            receptionCounter[idx] = make_pair(receptionWatingQ.front(), 0);
            receptionWatingQ.pop();
             //cout << "idx : " << idx << ' ' << receptionCounter[idx].first << '\n';
            if (idx == A) Ai.push_back(receptionCounter[A].first);
            idx++;
        }
         //cout << "maintenance : " << '\n';
        idx = 1;
        // 정비 대기실 (큐) --> 정비 창구
        while (idx != m + 1 && !maintenanceWatingQ.empty()) {
            if (maintenanceCounter[idx].first != 0) {
                idx++;
                continue;
            }
            maintenanceCounter[idx] = make_pair(maintenanceWatingQ.front(), 0);
            maintenanceWatingQ.pop();
             //cout << "idx, cntNum : " << idx << ' ' << maintenanceCounter[idx].first << '\n';
            if (idx == B) Bi.push_back(maintenanceCounter[B].first);
            idx++;
        }
        // 1초씩 증가 시켜주는 코드
        for (int i = 1; i <= n; i++) {
            if (receptionCounter[i].first == 0) continue;
            receptionCounter[i].second++;
        }
        for (int i = 1; i <= m; i++) {
            if (maintenanceCounter[i].first == 0) continue;
            maintenanceCounter[i].second++;
        }
    }
    /*for (int i = 0; i < Ai.size(); i++) cout << Ai[i] << ' '; cout << '\n';
    for (int i = 0; i < Bi.size(); i++) cout << Bi[i] << ' '; cout << '\n';*/
    for (int i = 0; i < Ai.size(); i++) {
        for (int j = 0; j < Bi.size(); j++) {
            if (Ai[i] == Bi[j]) {
                ans += Ai[i];
                break;
            }
        }
    }
    if (ans == 0) ans = -1;
    return ans;
}
int main(int argc, char** argv) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int test_case, T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> n >> m >> k >> A >> B;
        for (int i = 1; i <= n; i++) cin >> receptionTime[i];
        for (int i = 1; i <= m; i++) cin >> maintenanceTime[i];
        for (int i = 1; i <= k; i++) cin >> guestTime[i];
        int ans = solve();
        cout << "#" << test_case << ' ' << ans << '\n';
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}