9280 진용이네 주차타워

진용이네 주차타워 URL

Solution

import java.io.*;
import java.util.*;

class Solution {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int[] cost = new int[N]; //비용
			int[] weight = new int[M]; //무게
			int[] p = new int[N]; //주차공간
			int answer = 0;
			
			Queue<Integer> q = new LinkedList<>();
			Queue<Integer> cq = new LinkedList<>();
			
			//주차 비용
			for (int i = 0; i < N; i++) {
				cost[i] = Integer.parseInt(br.readLine());
			}
			//차량 무게
			for (int i = 0; i < M; i++) {
				weight[i] = Integer.parseInt(br.readLine());
			}
			
			for (int i = 0; i < M*2; i++) {
				int x = Integer.parseInt(br.readLine());
				q.add(x);
			}
			
			int cnt = 0;
			while (!q.isEmpty()) {
				int num;
				
				if (cnt < N && !cq.isEmpty()) {
					num = cq.poll();
					
					for (int i = 0; i < N; i++) {
						if (p[i] == 0) {
							p[i] = num;
							answer += weight[num-1] * cost[i];
							cnt++;
							break;
						}
					}
				} else {
					num = q.poll();
					
					if (num > 0) {
						if (cnt < N) {
							for (int i = 0; i < N; i++) {
								if (p[i] == 0) {
									p[i] = num;
									answer += weight[num-1] * cost[i];
									cnt++;
									break;
								}
							}
						} else {
							cq.offer(num);
						}
					} else {
						for (int i = 0; i < N; i++) {
							if (p[i] == -1 * num) {
								p[i] = 0;
								cnt--;
							}
						}
					}
				}
			}
			
			
			
			System.out.println("#" + t + " " + answer);
		}
	}
}

배운점

풀이

1. 3개의 자료구조가 필요한 문제이다. (주차 공간으로 사용할 배열) (M개의 입력을 받을 큐) (주차 대기로 사용할 큐)

2. 입력을 받으면 cnt는 주차된 차량 수, num은 poll한 값을 담는다.

3. 주차공간이 생겼을 때 대기 공간에 차량이 있다면 우선적으로 넣어준다.

4. 주차공간이 있을 때 대기 공간에 차량이 없다면 다음 q에서 poll한 값을 넣어준다.

5. 만약 주차공간이 없다면 대기 공간에 offer 한다.

6. 출차할 경우 배열의 인덱스를 0으로 초기화한다.

조건이 많아 복잡한 문제였다. 내가 시도한 방법은 주차공간에 주차할 때마다 방문처리를 해 주는 방식이었는데 대기 차량을 체크해 주지 못하였고, 어떤 차량이 방문했는지 체크가 안되었다. 모든 조건을 먼저 정리한 후에 풀이를 시작하는 연습이 필요하다.