백준 - 주차장(5464번) (자바)

문제 설명

시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영된다. 차가 주차장에 도착하면, 주차장 관리인이 비어있는 주차 공간이 있는지를 검사한다. 만일 비어있는 공간이 없으면, 차량을 빈 공간이 생길 때까지 입구에서 기다리게 한다. 만일 빈 주차 공간이 하나만 있거나 또는 빈 주차 공간이 없다가 한 대의 차량이 주차장을 떠나면 곧바로 그 장소에 주차를 하게 한다. 만일 빈 주차 공간이 여러 곳이 있으면, 그 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 만일 주차장에 여러 대의 차량이 도착하면, 일단 도착한 순서대로 입구의 대기장소에서 줄을 서서 기다려야 한다. 대기장소는 큐(queue)와 같이, 먼저 대기한 차량부터 주차한다.

주차료는 주차한 시간이 아닌 차량의 무게에 비례하는 방식으로 책정된다. 주차료는 차랑의 무게에다 주차 공간마다 따로 책정된 단위 무게당 요금을 곱한 가격이다.

주차장 관리원은 오늘 M대의 차량이 주차장을 이용할 것이라는 것을 알고 있다. 또한, 차량들이 들어오고 나가는 순서도 알고 있다.

주차 공간별 요금과 차량들의 무게와 출입 순서가 주어질 때, 오늘 하룻동안 주차장이 벌어들일 총 수입을 계산하는 프로그램을 작성하라.

입력

반드시 표준 입력으로부터 다음의 데이터를 읽어야 한다.

첫 번째 줄에는 정수 N과 M이 빈칸을 사이에 두고 주어진다.

그 다음 N개의 줄에는 주차 공간들의 단위 무게당 요금을 나타내는 정수들이 주어진다. 그 중 s번째 줄에는 주차 공간 s의 단위 무게당 요금 Rs가 들어있다.

그 다음 M개의 줄에는 차량들의 무게를 나타내는 정수들이 주어진다. 차량들은 1 부터 M 까지 번호로 구분되고, 이 번호는 출입 순서와는 상관없다. 이 M개의 줄 중 k번째 줄에는 차량 k의 무게를 나타내는 정수 Wk가 들어있다.

그 다음 2*M 개의 줄에는 차량들의 주차장 출입 순서를 나타내는 정수들이 한 줄에 하나씩 주어진다. 양의 정수 i는 차량 i가 주차장에 들어오는 것을 의미하고, 음의 정수 -i는 차량 i가 주차장에서 나가는 것을 의미한다. 주차장에 들어오지 않은 차량이 주차장에서 나가는 경우는 없다. 1 번부터 M 번까지 모든 차량은 정확하게 한 번씩 주차장에 들어오고, 한 번씩 주차장에서 나간다. 또한 입구에서 대기 중인 차량이 주차를 하지 못하고 나가는 경우는 없다.

1 ≤ N ≤ 100 주차 공간의 수

1 ≤ M ≤ 2,000 차량의 수

1 ≤ Rs ≤ 100 주차 공간 s의 단위 무게당 요금

1 ≤ Wk ≤ 10,000 차량 k의 무게

출력

출력은 반드시 표준 출력으로 하여야 하며, 하나의 줄에 한 개의 정수를 출력한다. 이 정수는 오늘 하룻동안 주차장이 벌어들인 총 수입이다.

예제 입력 1

3 4 2 3 5 200 100 300 800 3 2 -3 1 4 -4 -2 -1

예제 출력 1

5300

예제 입력 2

2 4 5 2 100 500 1000 2000 3 1 2 4 -1 -3 -2 -4

예제 출력 2

16200

힌트

차량 3이 주차 공간 1에 주차한다. 주차료는 300 * 2 = 600 이다.

차량 2가 주차 공간 2에 주차한다. 주차료는 100 * 3 = 300 이다.

차량 1이 차랑 3이 떠난 주차공간 1에 주차한다. 주차료는 200 * 2 = 400 이다.

차량 4가 마지막 남은 주차 공간 3에 주차한다. 주차료는 800 * 5 = 4,000 이다.

이 문제를 보고 저는 먼저 주차공간을 우선순위 큐(주차장 번호에 따른) 에 넣어놓고 주차장에 차가 들어올 때마다 해당 주차장번호를 큐에서 빠지게 학고 차가 나가면 큐에 다시 주차장 번호가 주차공간 큐에 넣어 주는 식으로 구현하면 되겠다고 방향을 잡았습니다.

이 과정에서 주차공간이 없으면 대기하는 큐에 해당 차량들을 넣어주었고

주차장에 있는 차들은 언제 빠져나갈지 모르기 때문에 Map을 이용해 관리했습니다.

이 Map에는 차량번호와 주차장번호, 주차장의 단위무게당 비용을 저장하기 위해 주차장 번호와 단위무게당 비용을 저장할 수 있는 class를 하나 만들어서 구현했습니다.

코드

public class exam1 {

//주차장 번호와 단위무게당 비용을 저장할 class
static class ParkingLot{
    int no;
    int weightPrice;

    public ParkingLot(int no, int weightPrice) {
        this.no = no;
        this.weightPrice = weightPrice;
    }
}

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[] carWeight = new int[M+1];
    int income = 0;

    //주차요금을 저장할 Map
    HashMap<Integer,Integer> parkingPrice = new HashMap<>();
    //주차장의 상태를 나타낼 PriorityQueue 1 ~ N 까지 저장
    PriorityQueue<Integer> parkingPlace = new PriorityQueue<>();
    IntStream.rangeClosed(1,N).forEach(x->parkingPlace.offer(x));

    for (int i = 0; i < N; i++) {
        //1~N까지의 주차요금 저장
        parkingPrice.put(i+1,Integer.parseInt(br.readLine()));
    }

    for (int i = 1; i <= M; i++) {
        //1~M까지의 자동차의 무게 저장
        carWeight[i] = Integer.parseInt(br.readLine());
    }
    //주차장 오간 기록을 저장하는 배열
    int[] records = new int[2*M];

    for (int i = 0; i < 2*M; i++) {
        records[i] = Integer.parseInt(br.readLine());
    }
    //주차장에 들어와있는 차와 주차장, 주차장번호를 기록한 Map
    HashMap<Integer,ParkingLot> enteredMap = new HashMap<>();
    //주차장이 꽉차서 기다리고 있는 차들을 저장한 큐
    Queue<Integer> standBy = new LinkedList<>();

    for (int i = 0; i < records.length; i++) {
        if(records[i] > 0){
            //주차장에 들어왔음을 의미함.

            if(parkingPlace.isEmpty()){
                //주차장이 꽉 찼는데 차가 계속 들어왔기 때문에 stanBy 큐에 넣어주었다.
                standBy.offer(records[i]);
                continue;
            }
            enteredMap.put(records[i],new ParkingLot(parkingPlace.peek(),parkingPrice.get(parkingPlace.poll())));
        }else {
            int num = records[i] * -1;
            //주차장에서 나갔음을 의미함.
            //차량의 무게
            int weight = carWeight[num];
            //공원에서 단위무게 비용
            int parkPrice = enteredMap.get(num).weightPrice;
            //인컴에 차량의 무게 * 공원의 단위무게 비용값을 누적한다.
            income += weight * parkPrice;
            //주차장에서 나갔기 때문에 enteredMap에 들어있는 주차장 번호를 다시 parkingPlace 큐에 넣어준다.
            parkingPlace.offer(enteredMap.get(num).no);

            if(!standBy.isEmpty()) {
                enteredMap.put(standBy.poll(), new ParkingLot(parkingPlace.peek(), parkingPrice.get(parkingPlace.poll())));
            }
            enteredMap.remove(num);
        }
    }
    System.out.println(income);

}

}
저는 꽤 복잡하게 풀었는데 다른 분들은 저처럼 이렇게 많은 자료구조를 사용하지 않고도..잘 하셨더라구요.. 그래서 더욱 배움이 필요하다고 느꼈습니다...!!! 아자아자