[SWEA] 9280. 진용이네 주차타워

문제

부지런한 진용이는 정문 앞에서 유료 주차장 운영하고 있다. 이 주차장은 1 부터 n 까지 번호가 매겨진 n 개의 주차 공간을 가지고 있다.
매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 다음과 같은 방식으로 운영된다.

 

• 차가 주차장에 도착하면, 진용이는 비어있는 주차 공간이 있는지 검사한다.
   
• 비어있는 공간이 없다면, 빈 공간이 생길 때까지 차량을 입구에서 기다리게 한다.
   
• 빈 주차 공간이 있으면 진용이는 곧바로 주차를 시키며, 주차 가능한 공간 중 번호가 가장 작은 주차 공간에 주차하도록 한다.
   
• 만약 주차를 기다리는 차량이 여러 대라면, 입구의 대기장소에서 자기 차례를 기다려야 한다. 운전자들은 예의가 바르기 때문에 새치기를 하지 않는다.

 

주차요금은 차량의 무게와 주차 공간마다 따로 책정된 단위 무게당 금액을 곱한 가격이다. 진용이네 주차장에서는 종일 이용권만을 판매하기 때문에 이용시간은 고려하지 않는다.
 

진용이는 오늘 주차장을 이용할 m 대의 차량들이 들어오고 나가는 순서를 알고 있다.
진용이의 주차장이 오늘 하루 벌어들일 총 수입을 계산하는 프로그램을 작성하라.

 

• 첫 번째 줄에 자연수  n 과  m 이 주어진다. (1 ≤ n  ≤ 100, 1 ≤ m  ≤ 2000)
• n 개의 줄에 i 번째 주차 공간의 단위 무게당 요금 Ri 가 정수로 주어진다. (1 ≤ Ri  ≤ 100)
• m 개의 줄에 차량 i 의 무게 Wi 가 정수로 주어진다. 차량번호 i 와 차량의 도착 순서는 아무런 관계가 없다. (1 ≤ Wi  ≤ 10000)
• 이후  2m 개의 줄에 차량들의 주차장 출입 순서가 하나의 정수  x 로 주어진다.
  주어진 정수 x 가 양수면, x 번 차가 주차장에 들어옴을 뜻한다.
  x 가 음수면, -x 번 차가 주차장을 나감을 뜻한다.

 

풀이방법

큐(Stack) 자료구조의 선입선출(FIFO, First In First Out)을 이용한다.

 

1) 세 개의 자료구조가 필요하다. m개의 입력을 받아들일 큐, 주차장으로 사용될 배열, 주차장이 가득 찼을 경우를 대비한 큐

 

2) m개의 입력을 큐에 넣는다. 배열을 0으로 초기화한다.

 

3) 큐에서 값을 하나씩 뽑아 배열에 낮은 인덱스 순으로 원소에 큐의 값을 넣어준다.

 

4) 큐에서 음수가 나올 경우 -1을 곱해 해당하는 원소의 값을 0으로 바꿔준다.

 

4-1) 큐에서 양수가 나왔는데 배열이 모두 0이 아닐 때, 1)에서 만들어준 대비 큐에 넣는다.

 

5) 4)의 단계가 나올때까지 4-1)을 반복한다.

 

6) 4)의 단계가 나왔다면 대비 큐에서 값을 뽑아 배열에 넣는다.

 

7) 4) - 6)의 과정을 m을 담은 큐가 빌 때까지 반복한다.

 

소스코드

package samsung;

import java.util.*;

public class s_9280 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int sum = 0;
			int[] r = new int[n];
			int[] w = new int[m];
			int[] p = new int[n];
			
			Queue <Integer> q = new LinkedList();
			Queue <Integer> rq = new LinkedList();
			
			for(int i = 0; i < n; i++) {
				r[i] = sc.nextInt();
			}
			
			for(int i = 0; i < m; i++) {
				w[i] = sc.nextInt();
			}
			
			for(int i = 0; i < 2 * m; i++) {
				int tmp = sc.nextInt();
				q.add(tmp);
			}
			
			int cnt = 0;
			
			while(!q.isEmpty()) {
				int num;
				if(cnt < n && !rq.isEmpty()) {
					num = rq.poll();
					for(int i = 0; i < n; i++) {
						if(p[i] == 0) {
							p[i] = num;
							sum += w[num - 1] * r[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;
									sum += w[num - 1] * r[i];
									cnt++;
									break;
								}
							}
						}
						else {
							rq.add(num);
						}
					}
					else {
						for(int i = 0; i < n; i++) {
							if(p[i] == -1 * num) {
								p[i] = 0;
								cnt--;
							}
						}
					}
				}
			}
			System.out.println("#" + t + " " + sum);
		}
	}
}