[Boj_14464] 소가 길을 건너간 이유 4

📎 문제 링크

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

 

▸ 문제

농부 존의 소들은 효율적으로 길을 건너는 방법을 터득하고 있다. 그들은 길 건너기의 달인인 닭의 도움을 받기로 했다.

안타깝게도 닭은 매우 바쁜 동물이라, 소를 도와줄 시간이 별로 없다. 농장에 C마리(1 ≤ C ≤ 20,000)의 닭이 있고, 1번부터 C번까지 번호가 붙어 있다. i번 닭은 정확히 Ti초에만 소를 도와줄 수 있다. 하지만 닭은 길 건너기의 달인이므로 소를 데리고도 순식간에 길을 건널 수 있다. 소는 할 일이 없어서 여유롭게 길을 건널 수 있다. 소는 총 N마리(1 ≤ N ≤ 20,000)가 있고, 마찬가지로 1번부터 N번까지 번호가 붙어 있다. j번 소는 Aj초부터 Bj초까지 길을 건널 수 있다. j번 소가 i번 닭의 도움을 받아 길을 건너려면  Aj ≤ Ti ≤ Bj를 만족해야 한다.

소는 최대 한 마리의 닭에게만 도움을 받을 수 있고, 닭 역시 최대 한 마리의 소만 도와줄 수 있다. 도움을 받을 수 있는 소가 최대 몇 마리인지 구해보자.

 

▸ 입력

첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(Aj ≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다.

 

▸ 출력

도움을 받을 수 있는 소가 최대 몇 마리인지 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 1
• 🔔  문제 유형 : 자료구조, 그리디 알고리즘, 우선순위 큐
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

우선순위 큐를 사용해서 해결할 수 있는 문제였다.

 

가장 빠르게 도움을 줄 수 있는 닭을 찾기 위해 Ti를 기준으로 오름차순으로 정렬한다.

아래와 같은 케이스의 경우를 대비하기 위해 소는 Bj 기준으로, Bj가 같다면 Aj를 기준으로 오름차순으로 정렬한다.

Ti : 2, 4

Aj Bj : 1 5, 2 3

 

한 마리의 소씩 순회하며 도움을 받은 적절한 닭을 찾아주면 된다.

 

위 풀이대로 코드를 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 22244KB
시간 : 440ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int c, n;
    static int[] chickens;
    static PriorityQueue<Pos> cows;
    static public class Pos implements Comparable<Pos> {
        int start; int end;
        public Pos (int start, int end) {
            this.start = start; this.end = end;
        }
        @Override
        public int compareTo(Pos o) {
            if (this.end != o.end) return this.end - o.end;
            return this.start - o.start;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        c = Integer.parseInt(st.nextToken()); // 닭의 수
        n = Integer.parseInt(st.nextToken()); // 소의 수

        chickens = new int[c];
        for (int i = 0; i < c; i++) {
            chickens[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(chickens);

        cows = new PriorityQueue<>();
        int s, e;
        for (int i = 0; i < n ; i++) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            cows.offer(new Pos(s, e));
        }

        // 몇 마리의 소가 닭에게 도움을 받을 수 있는지
        System.out.println(sol());
    }

    private static int sol() {
        int cnt = 0;

        while (!cows.isEmpty()) {
            // 소는 최대 한번 닭의 도움을 받을 수 있음
            Pos now = cows.poll();

            for (int i = 0; i < c; i++) {
                // 소가 닭에게 도움을 받을 수 있음
                if (chickens[i] >= now.start && chickens[i] <= now.end) {
                    cnt++;
                    // 닭은 최대 한번만 소를 도와줄 수 있음
                    chickens[i] = -1;
                    break;
                }
            }
        }

        return cnt;
    }
}

 

해결 완료 ! 🔥