[백준] 5464번. 주차장(JAVA)

문제

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

---

풀이(22분)

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

public class Main {

    // 차가 도착하면 공간이 비어있는지부터 검사
    // 비어있지 않다면 입구에서 기다리게 함
    // 하나만 있거나 하나가 떠나면 그 자리에 주차
    // 여러 곳이 있으면 번호가 가장 작은 곳에 주차
    // 여러 대의 차량이 오면 온 차부터 대기
    // 주차료는 주차한 시간이 아닌 차량의 무게에 비례
    // 주차료  = 차량의 무게  x 주차 공간마다 책정된 단위 무게당 요금
    // M대의 차량이 올 것이라는걸 암. 차량이 들어오고 나가는 순서도 암.
    // 오늘 벌어들일 총 수입은
    //
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[] charge = new int[n + 1]; // 공간들의 요금
        PriorityQueue<Integer> freeSpace = new PriorityQueue<>();
        int[] weight = new int[m + 1]; // 차량들의 무게
        int[] order = new int[2*m + 1]; // 차량들의 출차 순서
        int[] parking = new int[m + 1];

        for(int i = 1; i <= n; i++){
            charge[i] = Integer.parseInt(br.readLine());
            freeSpace.add(i);
        }

        for(int i = 1; i <= m; i++){
            weight[i] = Integer.parseInt(br.readLine());
        }

        for(int i = 1; i <= 2 * m; i++){
            order[i] = Integer.parseInt(br.readLine());
        }

        int answer = 0;

        Queue<Integer> queue = new LinkedList<>();

        for(int i = 1; i <= 2 * m; i++){
            int curOrder = order[i];
            if(curOrder > 0){ // 차가 들어오는 경우
                if(freeSpace.size() > 0 && freeSpace.size() <= n){ // 공간이 있다면
                    parking[curOrder] = freeSpace.poll(); // 주차한 지역 저장
                    answer += charge[parking[curOrder]] * weight[curOrder]; // 비용 부과
                    continue;
                }
                queue.add(curOrder);
                continue;
            }
            curOrder *= -1; // 일단 양수로 만들기
            freeSpace.add(parking[curOrder]); // 주차되어있던 차 빼주기
            if(!queue.isEmpty()){
                int nextCar = queue.poll(); // 제일 먼저 대기중인 차
                parking[nextCar] = freeSpace.poll(); // 주차한 지역 저장
                answer += charge[parking[nextCar]] * weight[nextCar]; // 비용 부과
            }
        }

        System.out.println(answer);
    }
}

---

문제 풀이 전략

 

주차 공간은 비용에 관계없이 작은 숫자부터 배치해주어야 하기에 우선순위 큐를 사용해 주었다.

 

이후 풀이는 다음과 같다.

먼저 숫자가 양수인지 음수인지 판별한다.

 

1. 양수라면

1-1. 여유 공간이 있는지 확인한다. -> 문제에서 의도하지는 않겠지만 최대 n개의 공간이 있다는 것도 확인한다.

-> 이렇게 하면 디버깅에서 효율적으로 검사가 가능하다.

1-2. 차량 번호에 따라 주차한 공간을 저장해 준다.

1-3. 정답에 비용을 계산한다.

1-4. 여유 공간이 없다면 대기 큐에 넣는다.(이때의 대기 큐는 우선순위 큐가 아닌 말 그대로의 큐이다.)

 

2. 음수라면

2-1. 먼저 인덱스로 사용하기 위해 음수를 양수로 변환해 준다.

2-2. 우선순위 큐에 현재 차가 나간 공간을 추가해 준다.

2-3. 주차하고자 대기 중인 큐가 있다면 주차를 해주고, 비용을 부과한다.