[JAVA-D3] SWEA 9280 - 진용이네 주차타워

SW Expert Academy

 

✅ 문제 요약

단위 무게당 요금과 자동차의 무게 그리고 자동차가 들어오고 나가는 순서가 주어진다.

이때 벌어들이는 수입을 구하라.

 

🤔 문제 풀이

풀어볼만한 구현 문제였다.

 

<사용한 자료구조>

배열 R : 단위 무게당 요금 저장

배열 W : 자동차 무게 저장

큐 q : 자동차 입,퇴장 순서 저장

배열 park : 주차 공간 현황 저장

배열 info : 어떤 차가 어디에 주차했는지 정보 저장

큐 wait : 주차 자리가 없어 기다리는 차량들 순서대로 저장

 

단위 무게당 요금과 자동차의 무게를 배열에 담아놓았고 자동차의 입,퇴장 순서를 큐에 담아 놓았다. 

 

큐에서 하나씩 자동차의 입장, 퇴장 정보를 꺼내오며 주차 자리를 탐색했다.

주차가 가능할 때 가장 낮은 번호부터 주차를 하기 때문에 자리 탐색은 1번부터 n까지 오름차순으로 진행하며

만약 해당 배열 값이 0인 경우 인덱스를 리턴했고 모든 배열 값이 0이 아닌, 주차할 공간이 없는 경우

-1을 리턴했다.

 

만약 주차를 할 수 있다면 이미 해당 자리는 주차 되었다는 표시를 위해 park[주차할 공간] + 1을 해주었고

요금 계산과 해당 차량이 어디에 주차되어있는지를 배열에 저장해줬다. 

처음에 실수를 했었는데,

자리가 없을 때 늦게 온 차량이 대기하도록 하기 위해 q에서 꺼내지 않도록 peek()을 사용했지만

만약 차들이 나가지않고 처음부터 연속적으로 들어와 꽉 차있는 경우 (예제 2와 같은 경우) 무한 루프에 걸리게 된다.

따라서 일단 q.poll()로 입 퇴장 정보를 받은 뒤 대기하는 차량들은 wait 큐를 통해 관리해주었다.

 

차량이 나갈 경우 park[주차한 자리] - 1로 비어있음을 나타냈다. 이때 대기하는 차량이 있다면

wait 큐에서 꺼내와 주차를 시키고 요금 계산을 했다.

 

🚨CODE

import java.util.*;
import java.io.*;
 
public class Solution {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int testCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= testCase; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int[] R = new int[n+1];
            int[] W = new int[m+1];
             
            // 단위 무게당 요금 R
            for(int i = 1; i<=n; i++) {
                R[i] = Integer.parseInt(br.readLine());
            }
             
            // 차량의 무게 W
            for(int i = 1; i<=m; i++) {
                W[i] = Integer.parseInt(br.readLine());
            }
             
            Queue<Integer> q = new LinkedList<>();
            // 들어오는 차량의 수의 2배만큼 입력을 받음, 들어오면 반드시 나가게 되어있기 때문에
            for(int i = 0; i<m*2; i++) {
                int info = Integer.parseInt(br.readLine());
                q.add(info);
            }
            int[] park = new int[n+1];
            int[] info = new int[m+1];
            int sum = 0;
            Queue<Integer> wait = new LinkedList<>();
             
            while(!q.isEmpty()) {
                int car = q.poll();
                 
                // 차량이 들어왔다면
                if(car > 0) {
                    // 주차 자리 탐색
                    int parkArea = findPark(park);
                    // 주차 자리가 있다면
                    if(parkArea > 0) {
                        park[parkArea] += 1;
                        sum += W[car] * R[parkArea];
                        info[car] = parkArea;
                    } 
                    // 자리가 없다면
                    else {
                        wait.add(car);
                    }
                }
                // 차량이 나간다면
                else {
                    int parkedArea = info[Math.abs(car)];
                    park[parkedArea] -= 1;
                     
                    // 기다리는 차가 있다면
                    if(wait.size() >= 1) {
                        int waiter = wait.poll();
                        // 방금 나간 차 자리에 주차
                        info[waiter] = parkedArea;
                        park[parkedArea] += 1;
                        sum += W[waiter] * R[parkedArea];
                    }
                }
                 
            }
            bw.write(String.format("#%d %d\n", t, sum));
        } // end of test case
        bw.flush();
    }
    public static int findPark(int[] park) {
        for(int i = 1; i<=park.length-1; i++) {
            if(park[i] == 0)
                return i;
        }
        return -1;
    }
}