[백준] 1931번 회의실 배정

문제링크: 백준 1931번 회의실 배정

---

1. 아이디어

회의실 배정은 전형적인 그리디 알고리즘.
회의클래스를 따로 만들어 for문 돌며 리스트에 회의객체(start와 end 시간) 담기.
가장 빨리 끝나는 회의를 계속 선택해나가야 하므로
끝나는 시간 기준으로 Collections.sort로 정렬한 후
회의 선택해나가기

1. 시간복잡도

회의의 수 N: 1 <= N <= 100,000
회의 시간: 0 <= 회의시간 <= 2^31 - 1
첫번째 for문: O(N)
Collections.sort정렬: O(N)
List 돌면서 회의 선택해나가기: O(N)

=> 총 시간복잡도: O(3N) == O(N)

1. 자료구조

회의의 수 N: 1 <= N <= 100,000 ==> int 가능
회의 시간: 0 <= 회의시간 <= 2^31 - 1 ==> int 범위 넘음. ==> 시간을 다룰 땐 Long 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    // 회의 클래스
    static class Meeting {
        long start;
        long end;
        Meeting() {};
        Meeting(long start, long end) {
            this.start = start;
            this.end = end;
        }
    }
    
    public static void solution(Long[][] arr, int N, ArrayList<Meeting> mt, int a) {
        int answer = a; // 회의 개수
        Long curTime = 0L; // 현재 시간
        for (Meeting item : mt) { // List 돌면서
            if(curTime <= item.start) { // 시작시간 안지났으면 회의 선택
                curTime = item.end; // 현재시간은 해당 회의 끝나는 시간으로 업데이트
                answer++; // 회의 개수 추가
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int a = 0;
        Long[][] arr = new Long[N][2];
        for (int i = 0; i < arr.length; i++) {
            String[] s = br.readLine().split(" ");
            arr[i][0] = Long.parseLong(s[0]);
            arr[i][1] = Long.parseLong(s[1]);
        }
        ArrayList<Meeting> mt = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            mt.add(new Meeting(arr[i][0], arr[i][1]));
        }
        // 여기서 문제 이슈 발생.
        // 회의의 시작시간과 끝시간이 같을 수 있다는 조건이 있는데,
        // 끝나는 시간으로 정렬할 경우 시작시간과 끝시간이 같은 회의들은 처리가 안되는 경우 발생
        // 정렬을 할 때 두가지 조건으로 정렬할 수 있냐는 문제에서
        // 시작시간으로 먼저 정렬하고 끝나는 시간으로 두번째 정렬을 해서 해결하기로 결정함
        // 회의의 수는 최대 10만개이므로 시간복잡도에 치명적이지 않을 것
        Collections.sort(mt, (x1, x2) -> (int)(x1.start - x2.start));
        Collections.sort(mt, (x1, x2) -> (int)(x1.end - x2.end));
        solution(arr, N, mt, a);
    }
}

• 학습내용

Collection.sort에서 정렬을 2가지 조건으로 해야할 때는
2순위 조건으로 먼저 정렬을 하고
1순위 조건으로 마지막에 정렬을 하면 됨.

• 다른 풀이

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());	// 회의 수
        int[][] time = new int[N][2];	// 회의 시간
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i][0] = Integer.parseInt(st.nextToken());
            time[i][1] = Integer.parseInt(st.nextToken());
        }
        // 최초 정렬 시 종료시간이 같으면 시작시간 순대로 정렬하는 것을 구현함!!
        Arrays.sort(time, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o2[1] == o1[1]) {	// 종료시간이 같으면
                    return o1[0] - o2[0]; // 시작시간 순대로 정렬하기!!
                } else {               // 종료시간이 다르면
                    return o1[1] - o2[1]; // 종료시간대로 정렬
                }
            }
        });

        int count = 1;
        int com = time[0][1];
        for (int i = 1; i < N; i++) {
            if(com <= time[i][0]) {
                count++;	// 끝나기 전에 시작시간이 잡히면 패스
                com = time[i][1];
            }
        }
        System.out.println(count);
    }
}

---

마지막 수정일시: 2022-06-30 16:57