[Baekjoon] 5464_주차장

Silver II

문제(출처: https://www.acmicpc.net/problem/5464)

---

< 주차장 >

 

문제 풀이 

 

빈 주차 공간은 우선순위 큐를, 대기하는 차량은 큐를 이용해서 문제를 해결했다.

 

 

 my solution (Java)

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

public class _5464_ { // 주차장

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int money[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			money[i] = Integer.parseInt(bf.readLine());
		}

		int car[] = new int[m + 1];
		for (int i = 1; i <= m; i++) {
			car[i] = Integer.parseInt(bf.readLine());
		}

		int arr[] = new int[m + 1];
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		Queue<Integer> temp = new LinkedList<>();

		for (int i = 1; i <= n; i++) {
			queue.add(i);
		}

		int result = 0;

		for (int i = 0; i < 2 * m; i++) {
			int num = Integer.parseInt(bf.readLine());
			if (num > 0) {
				if (queue.isEmpty()) {
					temp.add(num);
				} else {
					arr[num] = queue.poll();
				}
			} else {
				num = Math.abs(num);
				result += car[num] * money[arr[num]];

				if (!temp.isEmpty()) {
					arr[temp.poll()] = arr[num];
				} else {
					queue.add(arr[num]);
				}
			}
		}
		System.out.println(result);
	}
}

 

Main

변수)
n : 주차 공간 수
m : 주차장을 이용할 차량 수
money : 주차 공간들의 단위 무게당 요금
car : 차량들의 무게
arr : 각 차들의 주차 공간 번호 저장
queue : PriorityQueue <Integer> 빈 주차 공간
temp : Queue <Integer> 대기 차량
result : 총수입

 

- 주차 공간 수(n), 주차장을 이용할 차량 수(m) 입력

-  주차 공간들의 단위 무게당 요금 저장(money)

- 차량들의 무게 저장(car)

- queue에 비어있는 주차 공간 번호 저장

: 초기값이므로 전체 다 저장

- 차량들의 번호(num)를 입력받음

: 양수이면 들어오는 것이므로 주차 공간이 비어있는지 확인 후 비어있지 않다면 temp에 차량 번호 저장/ 비어있다면 주차장 번호 저장

: 음수이면 차량 무게 * 단위 무게당 요금 더한 후 대기 중인 차량이 있다면 주차 공간을 넣어주고 대기 중인 차량이 없다면 빈 주차 공간(queue)에 저장

- 총수입(result) 출력

 

---

---