[SW2477] 차량 정비소
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/SW Expert Academy

[SW2477] 차량 정비소

 SW Expert Academy - 차량 정비소 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy&categoryId=AV6c6bgaIuoDFAXy&categoryType=CODE&problemTitle=%EC%B0%A8%EB%9F%89&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

문제 입출력

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