[SWEA] 2477.차량 정비소 / 시뮬레이션

@시뮬레이션 / 1h 40m

엄청 어려워 보여서 이거 어떻게 하지 하고 당황했는데

문제에서 시키는 대로 차근차근 구현하면 생각보다 쉬운 문제였다.

큐와 우선순위 큐의 특성을 활용해서 풀었다.

+ 근데 구현 자체는 많이 어렵지 않았는데 조건이 약간 까다로워서 약간 시간이 걸렸다.

엄청 쉬운 문제는 아니지만 구현력 키우는데는 좋은 문제라고 생각함!

 

 

문제 링크

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

SW Expert Academy

 

구현 방법

 

1. 데이터

고객 정보는 고객 번호, 도착 시간, 기다린 시간, 접수창구 번호, 정비창구 번호를 담고 있는 Person 클래스로 선언한다.

일단 접수 창구와 정비 창구는 Person 클래스를 담을 수 있는 Person[창구 크기] 형으로 선언한다.

 

 

2. 접수 창구

1번 조건때문에 고객 도착 시간과 고객번호로 Comparable을 활용한 우선순위 큐를 써야하나 고민했지만

다행히 이 조건이 있어서 그냥 도착 순서대로 큐에 넣으면 됐다.

2번 조건은 어차피 창구크기만큼 for문을 돌릴 것이기 때문에 자동으로 창구번호가 작은 곳으로 들어가게 된다.

 

 

3. 정비 창구

정비 창구에서는 기다린 시간으로 정렬하고(기다리기 시작한 시간으로 해서 오름차순 정렬했다), 기다린 시간이 같을 경우 접수 창구 번호로 정렬해야 했기 때문에 조건을 2개 준 Comparable을 구현했다.

 

 

4. 코드 작성

while문 안에서 접수창구를 도는 for문 하나, 정비창구를 도는 for문 하나 총 두개의 for문을 돌린다.

이 때, 접수 창구에서 빠져나온 사람이 바로 정비창구를 들어가면 안 되기 때문에(다음 턴에 들어가야 한다)

임시 큐에 넣어놓고 for문 두개가 끝난 후에 정비창구 대기 큐에 넣어줬다. 이렇게 안해주면 시간이 꼬인다.

 

 

5. 종료 조건

처음에는 endCondition을 접수창구 큐가 비어있지 않거나 정비창구 큐가 비어있지 않을 때만 false 값으로 처리해줬는데, 그렇게 하면 접수창구에 이제 막 들어간 애가 있을 경우에는 잡지 못해서(tc 1번) tc 값이 틀리게 나왔다. 종료 조건 신경써야함!

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	
	private static class Person implements Comparable<Person> {
		int idx, arriveTime, waitTime, infoNum, fixNum;

		Person(int idx, int arriveTime) {
			this.idx = idx;
			this.arriveTime = arriveTime;
			this.waitTime = 0;
			this.infoNum = 0;
			this.fixNum = 0;
		}
		@Override
		public int compareTo(Person o) {
			int num = this.waitTime - o.waitTime;
			if (num == 0)
				num = this.infoNum - o.infoNum;
			return num;
		}
	}

	private static int N, M, K, A, B, infoTime[], fixTime[];
	private static Person[] infoList, fixList;
	private static Queue<Person> infoWait, tempWait, endPerson;
	private static PriorityQueue<Person> fixWait;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			infoWait = new LinkedList<>();
			tempWait = new LinkedList<>();
			endPerson = new LinkedList<>();
			fixWait = new PriorityQueue<>();
			
			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());
			
			infoTime = new int[N];
			infoList = new Person[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++)
				infoTime[i] = Integer.parseInt(st.nextToken());
			
			fixTime = new int[M];
			fixList = new Person[M];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++)
				fixTime[i] = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= K; i++)	//고객번호는 1부터 시작 
				infoWait.add(new Person(i, Integer.parseInt(st.nextToken())));
			
			int time = 0;
			while (true) {
				//접수, 정비 창구(배열) 모두 비고, 대기줄까지 비면 계속 true로 유지됨 
				boolean endCondition = true;
				//접수창구 
				for (int i = 0; i < N; i++) {
					if (infoList[i] == null) {
						if (infoWait.isEmpty()) continue;
						Person temp = infoWait.peek();
						if (time >= temp.arriveTime) {
							temp = infoWait.poll();
							temp.waitTime = 1;
							temp.infoNum = i;
							infoList[i] = temp;
						}
						endCondition = false;
					} else {
						infoList[i].waitTime++;
						endCondition = false;
					}
					if (infoList[i] != null && infoList[i].waitTime == infoTime[i]) {	//시간이 다 됐다
						infoList[i].waitTime = time;	//현재 시간을 넣어줘서 먼저기다린 애들부터 정비하게 하기 
						tempWait.add(infoList[i]);
						infoList[i] = null;
					}
				}
				
				//정비창구
				for (int j = 0; j < M; j++) {
					if (fixList[j] == null) {
						if (fixWait.isEmpty()) continue;
						Person temp = fixWait.poll();
						temp.waitTime = 1;
						temp.fixNum = j;
						fixList[j] = temp;
						endCondition = false;
					} else {
						fixList[j].waitTime++;
						endCondition = false;
					}
					if (fixList[j] != null && fixList[j].waitTime == fixTime[j]) {
						endPerson.add(fixList[j]);
						fixList[j] = null;
					}
				}
				
				//종료조건 
				if (infoWait.isEmpty() && fixWait.isEmpty() && endCondition) break;
				
				//접수창구에서 나온 애들 정비창구 대기줄에 넣어주기 
				while (!tempWait.isEmpty())
					fixWait.add(tempWait.poll());

				time++;
			}
			
			int personNumSum = 0;
			while (!endPerson.isEmpty()) {
				Person temp = endPerson.poll();
				if (temp.infoNum == A - 1 && temp.fixNum == B - 1)
					personNumSum += temp.idx;
			}
			if (personNumSum == 0) personNumSum = -1;
			sb.append("#" + t + " " + personNumSum + "\n");
		}
		
		System.out.println(sb);
	}
}

 

삽질 포인트

waitTime 써야할 곳에 arriveTime 써서 tc 4개 틀리게 나옴

빨리 잡아서 망정이지 못찾았으면 시간 꽤나 걸렸을 듯

 

그리고

이 조건도 뒤늦게 찾아서 삽질 할 뻔...

조심하자!

 

끝!