SW Expert Academy - 차량 정비소
문제 링크
문제 입출력
2 2 6 1 2
3 2
4 2
0 0 1 2 3 4
#1 7
문제 풀이
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
static int ans, T, N, M, K, A, B;
static int[] arr, brr, trr;
static PriorityQueue<Node> wa = new PriorityQueue<>((e1, e2) -> e1.no - e2.no);
static Node[] a;
static Queue<Node> wb = new ArrayDeque<>();
static Node[] b;
static List<Node> res = new ArrayList<>();
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
// 초기화
ans = 0;
wa.clear();
a = new Node[N + 1];
wb.clear();
b = new Node[M + 1];
res.clear();
arr = new int[N + 1]; // 0 dummy
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) arr[i] = Integer.parseInt(st.nextToken());
brr = new int[M + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= M; i++) brr[i] = Integer.parseInt(st.nextToken());
trr = new int[K + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= K; i++) trr[i] = Integer.parseInt(st.nextToken());
// 시뮬레이션
int time = 0;
while (true) {
if (res.size() == K) break;
// 해당 시간에 도착한 사람들 뽑아서 wa에 넣기
for (int i = 1; i <= K; i++) {
if (trr[i] == time) wa.add(new Node(i, -1, -1, 0, 0));
}
// 접수창구의 수만큼 wa 에서 빼내 a에 넣기
for (int i = 1; i <= N; i++) {
if (a[i] == null && !wa.isEmpty()) {
a[i] = wa.poll();
a[i].ai = i; // 접수창구 번호 입력
}
}
// 접수창구에서 보낸 시간 더하기
for (int i = 1; i <= N; i++) {
if (a[i] != null) a[i].atime++;
}
// 시간이 지나면 a에 꺼내서 wb에 넣기
for (int i = 1; i <= N; i++) {
if (a[i] != null && a[i].atime == arr[i]) {
wb.offer(a[i]);
a[i] = null; // 빈 접수창구 표시
}
}
// 정비창구의 수만큼 wb에서 꺼내 b에 넣기
for (int i = 1; i <= M; i++) {
if (b[i] == null && !wb.isEmpty()) {
b[i] = wb.poll();
b[i].bi = i;
}
}
// 정비창구에서 보낸 시간 더하기
for (int i = 1; i <= M; i++) {
if (b[i] != null) b[i].btime++;
}
// 다 했으면 나오기
for (int i = 1; i <= M; i++) {
if (b[i] != null && b[i].btime == brr[i]) {
res.add(b[i]);
b[i] = null; // 빈 접수창구 표시
}
}
time++;
}
ans = check();
if (ans == 0) ans = -1;
// 출력
sb.append("#").append(tc).append(" ").append(ans).append("\n");
}
System.out.println(sb.toString());
}
// A, B 창구를 이용한 고객을 찾는 함수
private static int check() {
int sum = 0;
for (Node node : res) {
if (node.ai == A && node.bi == B) sum += node.no;
}
return sum;
} // end check
static class Node {
int no;
int ai;
int bi;
int atime; // 접수창구에서 기다린 시간
int btime; // 정비창구에서 기다린 시간
public Node(int no, int ai, int bi, int atime, int btime) {
this.no = no;
this.ai = ai;
this.bi = bi;
this.atime = atime;
this.btime = btime;
}
@Override
public String toString() {
return "Node [no=" + no + ", ai=" + ai + ", bi=" + bi + ", atime=" + atime + ", btime="
+ btime + "]";
}
} // end Node
}
- 정말 리터럴리 시뮬레이션 문제.. 처음에는 못 풀거라고 예상했는데 차근차근 해보니 풀렸다. 성장했따 !! 🍀
- 관점은 적절한 자료구조를 사용하는 것이다.
- 일단 사용한 자료구조는 다음과 같다.
- 접수창구를 기다리는 줄 : PriorityQueue
- 접수창구 : Array
- 정비창구를 기다리는 줄 : Queue
- 정비창구 : Array
- 마지막 다 끝난 고객들 : List
- 접수 창구 같은 경우는 문제를 보면 고객번호가 낮은 순서대로 우선 접수를 한다고 되어있다.
- 따라서 접수 창구 웨이팅 줄을 낮은 번호순서대로 정렬할 수 있도록 우선순위큐를 사용하였다.
- 정비 창구 같은 경우는 먼저 기다리는 고객을 우선한다. 따라서 FIFO 를 따르는 큐를 사용하였다.
- 또한 하나의 고객을 뜻하는 Node 클래스를 선언하였다.
- 해당 클래스에서는 다음과 같이 속성을 선언하였다.
- no: 고객 번호
- ai: 고객이 들어간 접수창구 번호
- bi: 고객이 들어간 정비창구 번호
- atime: 고객이 접수창구에서 기다린 시간
- btime: 고객이 정비창구에서 기다린 시간
- while 문을 돌면서 시간을 재고 만약 다 끝난 고객이 K 라면 반복문을 끝낸다.
# SW 차량 정비소 # swea 차량정비소 java # sw 차량정비소 java
728x90
'✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 > SW Expert Academy' 카테고리의 다른 글
[SW2382] 미생물 격리 (0) | 2022.10.09 |
---|---|
[SW2383] 점심 식사시간 (0) | 2022.10.08 |
[SW3289] 서로소 집합 (0) | 2022.10.02 |
[SW3124] 최소 스패닝 트리 (0) | 2022.10.02 |
[SW7465] 창용 마을 무리의 개수 (0) | 2022.10.02 |