[Java] 백준 5464.주차장

 

문제

https://www.acmicpc.net/problem/5464

5464번: 주차장

풀이

내가 생각한 문제에서 요구사항은 다음과 같다.

주어진 조건대로 waiting Q를 구현하고싶은데 우선순위를 수정할줄 아느냐?

 

구현 문제를 풀때, 의미가 있는 변수 이름으로 설정해주면 내 코드를 보더라도 헷갈리지 않고 풀이할수 있다.

주석을 사용하는 대신 변수 네이밍으로 뜻만 보더라도 알아볼 수 있게 하였다.

 

풀이 알고리즘은 다음과 같다.

1. 현재 차가 들어올 타임일때
   1. 현재 대기 번호 뽑은 차량이 존재하거나 주차 공간이 없어 대기 번호를 발급 받아야할때
      1. 대기 번호를 발급한다.
   2. 주차장을 사용하고 이것을 기록한다
2. 현재 차가 나갈때
   1. 요금 정산을 한다.
   2. 대기 번호가 존재하면, 대기 번호에서 하나 뽑아 차량을 주차시킨다.

이해하기 쉽게 코드에 경로 주석을 적었다.

 

 

코드

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

public class Main {
    PriorityQueue<int[]> Empty_Position_Q;
    LinkedList<Integer> Car_Waiting_Q;
    int m[][];
    int cost[];
    int weight[];
    int info[];
    int parkIndex[];
    int size;
    int ans;
    BufferedWriter bw;
    public static void main(String args[]) throws IOException {
        Main m = new Main();
        m.solution();
    }
    public void solution() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();

        int N = Integer.parseInt(str.split(" ")[0]);
        int M = Integer.parseInt(str.split(" ")[1]);

        cost = new int[N+1];
        weight = new int[M+1];
        info = new int[2*M];
        parkIndex = new int[M+1];
        ans = 0;
        size = 0 ;

        for(int i =0 ; i< N;i++) {
            cost[i] = Integer.parseInt(br.readLine());
        }
        for(int i =1 ; i<= M;i++) {
            weight[i] = Integer.parseInt(br.readLine());
        }
        for(int i =0 ; i< 2*M;i++) {
            info[i] = Integer.parseInt(br.readLine());
        }

        Empty_Position_Q = new PriorityQueue<>((a,b)->a[0]-b[0]);
        Car_Waiting_Q = new LinkedList<>();

        for(int i =0 ;i < N;i++){
            Empty_Position_Q.offer(new int[]{i,cost[i]});
        }
        int t;
        int idx;
        int c[];
        int temp = 0;
        for(int i =0 ;i < 2*M; i++){
            if(info[i] > 0){ //1
                if(!Car_Waiting_Q.isEmpty() ||Empty_Position_Q.isEmpty()){//1-1
                    Car_Waiting_Q.offer(info[i]);//1-1-1
                }else{//1-1-2
                    c = Empty_Position_Q.poll();
                    parkIndex[info[i]] = c[0];
                }
            }else{//2
                t = info[i] * (-1);
                idx = parkIndex[t];
                parkIndex[t] = 0;
                Empty_Position_Q.offer(new int[]{idx, cost[idx]});
                ans += cost[idx] * weight[t];//2-1
                if(!Car_Waiting_Q.isEmpty()){//2-2
                    c = Empty_Position_Q.poll();
                    parkIndex[Car_Waiting_Q.poll()] = c[0];
                }
            }
        }

        bw.write(Integer.toString(ans));
        bw.close();
    }

}