[SWEA] 차량 정비소

[2477] 차량 정비소

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy

• [입력]
• [1] 접수 창구 개수 N, 정비 창구 개수 M, 방문 고객 수 K, 지갑을 두고간 접수 창구 번호 A, 정비 창구 번호 B
• [2] 각 접수 창구에서의 접수 시간 ai N개
• [3] 각 정비 창구에서의 정비 시간 bi M개
• [4] K명의 고객이 정비소에 도착하는 시간 K개
• [출력]
• 지갑을 두고 간 고객과 같은 접수 창구 A와 정비 창구 B를 이용한 고객들의 고객번호 합

 

 

Solution

• 접수 창구 대기열 q1, 정비 창구 대기열 q2, 접수 창구 배열 c1,  정비 창구 배열 c2를 만들었다.
• c1[0][i] : 창구별 서비스 시간, c1[1][i] : 서비스 받고 있는 고객 번호, i는 창구 번호 (c2 배열도 동일)
• while 문 {
• // 접수/정비 창고에서 서비스 시간이 끝난 고객을 뽑는 로직
• time++를 하면서 time과 [서비스가 끝나는 시간, t1/t2]이 동일해지는 시점에 창구 배열에 배정된 고객 번호를 해제한다.
• 접수가 끝난 경우에는 q2에 해당 대기자를 넣는다. 
• // q1, q2 대기열의 고객을 각각의 창구로 배정하는 로직
• (현재 시간 time > 고객의 정비소 도착 시간 && 접수/정비 창구에 빈 곳이 있을 때) 
• 해당 고객의 접수/정비가 끝나는 시간(t1, t2)을 기록 하고 창구 배열에 고객 번호를 넣는다.
• }
• while 문의 종료 조건은 {모든 고객에 대해 c1, c2 창구 번호가 정해졌을 경우 => 0이 아닌 경우}이다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M, k, A, B;
    static int[][] counter1, counter2;
    static List<Awaiter> awaiters;
 
    static class Awaiter {
        private int idx; // 대기자 번호
        private int arrived; // 정비소 도착 시간
        private int t1, t2; // 접수 창구에서 나가는 시간, 정비 창구에서 나가는 시간
        private int c1, c2; // 접수 창구 번호, 정비 창구 번호
 
        public Awaiter(int idx, int arrived) {
            this.idx = idx;
            this.arrived = arrived;
            this.t1 = 0;
            this.t2 = 0;
            this.c1 = 0;
            this.c2 = 0;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = stoi(br.readLine());
        StringTokenizer st;
        for (int tn = 1; tn <= tc; tn++) {
            st = new StringTokenizer(br.readLine());
            N = stoi(st.nextToken());
            M = stoi(st.nextToken());
            k = stoi(st.nextToken());
            A = stoi(st.nextToken());
            B = stoi(st.nextToken());
 
            counter1 = new int[2][N + 1];
            counter2 = new int[2][M + 1];
 
            awaiters = new ArrayList<>();
 
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                counter1[0][i] = stoi(st.nextToken());
                counter1[1][i] = -1;
            }
 
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= M; i++) {
                counter2[0][i] = stoi(st.nextToken());
                counter2[1][i] = -1;
            }
 
            awaiters.add(new Awaiter(0, 0));
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= k; i++) {
                awaiters.add(new Awaiter(i, stoi(st.nextToken())));
            }
 
            solve();
 
            int result = 0;
            for (Awaiter a : awaiters) {
                if (a.c1 == A && a.c2 == B) {
                    result += a.idx;
                }
            }
            System.out.println("#" + tn + " " + (result == 0 ? -1 : result));
        }
    }
 
    static void solve() {
        Queue<Awaiter> q1 = new LinkedList<>();
        for (Awaiter awaiter : awaiters) {
            if (awaiter.idx == 0)
                continue;
            q1.add(awaiter);
        }
        Queue<Awaiter> q2 = new LinkedList<>();
 
        int time = 0;
        int n = 0;
        int m = 0;
 
        while (true) {
            if (check())
                break;
            // 접수 창구
            for (int i = 1; i <= N; i++) {
                if (counter1[1][i] >= 0 && awaiters.get(counter1[1][i]).t1 == time) {
                    q2.add(awaiters.get(counter1[1][i]));
                    counter1[1][i] = -1;
                    n--;
                }
            }
            // 정비 창구
            for (int i = 1; i <= M; i++) {
                if (counter2[1][i] >= 0 && awaiters.get(counter2[1][i]).t2 == time) {
                    counter2[1][i] = -1;
                    m--;
                }
            }
 
            loop: while (!q1.isEmpty() && n < N) {// 접수 창구에 빈 자리가 있고
                if (q1.peek().arrived <= time) { // 정비소 도착시간 <= time -> 접수
                    for (int i = 1; i <= N; i++) {
                        if (counter1[1][i] == -1) {
                            counter1[1][i] = q1.poll().idx; // 접수
                            awaiters.get(counter1[1][i]).t1 = time + counter1[0][i]; // 접수 끝나는 시간 기록
                            awaiters.get(counter1[1][i]).c1 = i;
                            n++;
                            continue loop;
                        }
                    }
                } else {
                    break;
                }
            }
 
            loop: while (!q2.isEmpty() && m < M) {
                if (q2.peek().t1 <= time) {
                    for (int i = 1; i <= M; i++) {
                        if (counter2[1][i] == -1) {
                            counter2[1][i] = q2.poll().idx; // 정비
                            awaiters.get(counter2[1][i]).t2 = time + counter2[0][i]; // 정비 끝나는 시간 기록
                            awaiters.get(counter2[1][i]).c2 = i;
                            m++;
                            continue loop;
                        }
                    }
                } else {
                    break;
                }
            }
 
            time++;
        }
    }
 
    static boolean check() {
        for (Awaiter a : awaiters) {
            if (a.idx == 0)
                continue;
            if (a.c1 == 0 || a.c2 == 0) {
                return false;
            }
        }
        return true;
    }
 
    static int stoi(String s) {
        return Integer.valueOf(s);
    }
 
}