백준 알고리즘 9576번: 책 나눠주기

문제 정보

---

9576번: 책 나눠주기

 

핵심

---

전공 서적을 최대한 많은 학생들에게 나누어 줘야 하는 문제!

 

여기서 일단 정렬의 필요성은 느꼈는데, 어떤 식으로 정렬해야 할 지 고민하다가 위와 같은 케이스를 고려하여 기준을 선정해야 겠다고 생각하였다

끝나는 수를 기준으로 정렬해야 한다. 왜냐하면 시작점을 기준으로 정렬해 버리면 위 사진과 같은 결과가 나와서 최대 경우가 나오지 않는다

 

그 이후에는, 각 정렬된 학생들의 신청서(시작점~끝점)를 순회하면서 남아있는 책이 있다면 Pick(visited=true)하고 다음 학생을 찾아보면 된다

 

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testcase = Integer.parseInt(br.readLine());
        for(int i=0; i<testcase; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            boolean[] visited = new boolean[N+1];
            int M = Integer.parseInt(st.nextToken());

            int[][] applicant = new int[M][2];
            for(int j=0; j<M; j++) {
                st = new StringTokenizer(br.readLine());
                applicant[j][0] = Integer.parseInt(st.nextToken());
                applicant[j][1] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(applicant, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1]-o2[1];
                }
            });

            int result = 0;
            for(int m=0; m<M; m++) {
                for(int num=applicant[m][0]; num<=applicant[m][1]; num++) {
                    if(!visited[num]) {
                        visited[num] = true;
                        result++;
                        break;
                    }
                }
            }
            System.out.println(result);
        }
    }
}

applicant[][] 대신에 우선순위 큐를 쓰기도 하더라!

하지만 딱 한번만 정렬하면 되니까, 일반적인 정렬을 사용하여 풀이하였다!

 

Source Code on GitHub

---