[백준, Java] 5186번 : 파티를 열어라!!!

🔗 문제 링크

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

😮 문제 해결 방법

최대한 많은 차를 이용해 최대한 많은 친구들을 집에 보내줘야 최소한으로 집에서 재울 수 있다.

 

최대한 많은 친구들을 보내야하기 때문에 “차의 좌석수가 많은 순으로 내림차순" 정렬을 했다.

또한, 운전할 수 있는 친구들을 먼저 배치해주기 위해서 술을 마시지 않은 (S)기준으로 정렬했다.

 

자동차의 경우 우선순위 큐를 이용해 하나씩 빼면서 태울 수 있는 운전자를 배치한다. 배치된 운전자는 차에 탔다는 체크(ride)를 해주고 운전자 인원수를 1 증가시킨다.

운전자가 배치되는 경우 “태울 수 있는 좌석 - 1 (운전자)”를 지역별 태울 수 있는 인원수 배열(avilable)에 저장한다.

 

최대한 많은 운전자를 배치했다면, 이제 친구들 인원만큼 반복하면서 아직 차에 타지 않은 애들의 목적지와 동일한 지역의 차의 좌석이 남아있다면 넣어주고, 아닌 경우 카운팅해준다.

 

아직 차에 타지 않은 경우에만 애들을 태우는 조건으로 했기 때문에 운전자들도 함께 카운팅이된다.

이 때, 운전자를 배치하면서 카운팅한 운전자 인원수를 빼준다.

 

1. 친구들 리스트를 입력받으면서 술에 안취한 친구들을 카운팅한다.
2. 자동차 리스트와 친구들 리스트는 각각 “자동차의 좌석 내림차순”, “술에 안취한 친구들"로 정렬한다.
3. 자동차를 큐에서 하나씩 빼면서 운전자를 태울 수 있는지 판단하고, 태울 수 있다면 운전자가 탔다는 표시를 하고 운전자를 제외한 남은 좌석을 배열에 증가시킨다. 이 때, 운전자의 수도 카운팅한다.
4. 친구들 인원만큼 반복하면서 차에 타지 않은 친구들을 목적지와 동일한 차에 좌석이 남아있다면 태운다.
5. 이미 차에 탔거나, 탈수 없는 경우 카운팅을 한다.
6. 이미 차에 탄 경우도 함께 카운팅되기 때문에 운전자들의 인원수 만큼 빼준다. (운전자는 차에 탔지만 카운팅에 포함되기 때문이다.)

🚩 Java 코드

package com.second.algorithm.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_5186_파티를_열어라 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int K = Integer.parseInt(br.readLine()); // 테스트케이스

        for (int cases = 1; cases <= K; cases++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());   // 사람수
            int C = Integer.parseInt(st.nextToken());   // 자동차 수
            int L = Integer.parseInt(st.nextToken());   // 지역 수

            List<Friend> friends = new ArrayList<>();
            int driver = 0;
            for (int count = 0; count < N; count++) {
                st = new StringTokenizer(br.readLine());
                int location = Integer.parseInt(st.nextToken());
                String drunk = st.nextToken();

                // 운전할 수 있는 최대 인원을 구해놓는다.
                if(drunk.equals("S")) driver++;

                friends.add(new Friend(location, drunk));
            }

            List<Car> cars = new ArrayList<>();
            for (int count = 0; count < C; count++) {
                st = new StringTokenizer(br.readLine());
                int location = Integer.parseInt(st.nextToken());
                int available = Integer.parseInt(st.nextToken());

                cars.add(new Car(location, available));
            }

            int sleepPeople = sleepPeople(N, C, L, friends, cars, driver);
            System.out.println("Data Set "+cases +":");
            System.out.println(sleepPeople);
        }

        br.close();
    }

    private static int sleepPeople(int N, int C, int L, List<Friend> friends, List<Car> cars, int driver) {
        // 차가 없는 경우
        if(C == 0) return N;

        PriorityQueue<Car> carQueue = new PriorityQueue<>(cars);
        Collections.sort(friends);

        int[] available = new int[L+1];     // 차에 태울 수 있는 인원 배열
        boolean[] ride = new boolean[N];    // 친구들이 탔는지 안탔는지 판단하는 배열

        int rideDriver = 0;
        while(!carQueue.isEmpty()) {
            Car car = carQueue.poll();
            // 운전자만 먼저 태울수 있는 만큼 넣어주기
            for (int number = 0; number < driver; number++) {
                if(car.getLocation() == friends.get(number).getLocation() && !ride[number]) {
                    available[car.getLocation()] += car.getAvailable() - 1; // 위치별 운전자 제외하고 자동차에 탈 수 있는 인원수 추가
                    ride[number] = true;
                    rideDriver++;       // 운전하는 친구들 카운팅
                    break;
                }
            }
        }

        int count = 0;
        for (int number = 0; number < friends.size(); number++) {
            Friend friend = friends.get(number);
            if(available[friend.getLocation()] > 0 && !ride[number] ) available[friend.getLocation()]--;    // 자리가 남았고, 아직 차에 안탄 친구면 태우기
            else count++;
        }

        // 운전자 친구들은 이미 ride 배열이 true이므로 위에 친구들을 태울 때 운전자도 같이 카운팅된다.
        // 따라서, 운전자 친구들 만큼 빼준다.
        return count - rideDriver;
    }

    static class Friend implements Comparable<Friend> {
        private int location;
        private String drunk;

        public Friend(int location, String drunk) {
            this.location = location;
            this.drunk = drunk;
        }

        public int getLocation() {
            return location;
        }

        public String getDrunk() {
            return drunk;
        }

        @Override
        public int compareTo(Friend o) {
            if(o.drunk.equals(this.drunk))
                return Integer.compare(this.location, o.location);
            return o.drunk.compareTo(this.drunk);
        }
    }

    static class Car implements Comparable<Car> {
        private int location;
        private int available;

        public Car(int location, int available) {
            this.location = location;
            this.available = available;
        }

        public int getLocation() {
            return location;
        }

        public int getAvailable() {
            return available;
        }

        @Override
        public int compareTo(Car o) {
            if(this.location == o.location)
                return Integer.compare(o.available, this.available);
            return Integer.compare(this.location, o.location);
        }
    }
}