Q2 회의실 배정(1931번 문제)

 

 

 

📌 문제

문제)
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력)
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

출력)
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

📌 문제 분석❗️

분석	설명
입력	N개의 회의(첫째 줄), 시작 시간(N번째 줄), 끝나는 시간(N번째 줄)
출력	각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수
조건 1	회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
조건 2	회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

❗️ 진행할 회의를 선택할 때마다 최선의 선택을 해야한다.

그리디 알고리즘을 적용해볼 수 있는 문제이다.

 

❗️ 회의 시간이 짧을수록 회의를 많이할 수 있다.

회의 시간이 짧을수록 더 많은 회의를 할 수 있다. 따라서 회의를 선택할 때 종료 시간이 제일 작은 값을 선택해주는 것이 회의를 더 많이할 가능성이 있다. 

 

❗️ 종료 시간 값을 고려하기 전, 먼저 회의 리스트를 종료시간이 작은 순으로 정렬해야 한다. (오름차순)

회의 시간이 짧은 순으로 먼저 회의가 시작되어야 한다. 그럴 경우 선택지에서 종료시간이 가장 작은 것을 골라야하므로 종료시간을 기준으로 내림차순으로 정렬을 먼저 해야한다.

 

❗️ 조건  1 : 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

단 종료시간이 같을 경우, 시작시간에 대해서도 값을 빠른 순으로 정렬해야 한다.

3 6

6 6

6 6

같은 경우 답은 3이지만, 단순 종료시간만을 기준으로 정렬한다면

6 6

3 6

6 6

으로 답이 2가 나올 수 있다. 이러한 경우를 방지하기 위해 종료시간이 같을 경우 시작시간이 빠른 순으로 정렬해주어야 한다.

 

📌 선언

종류	이름	설명
BufferedReader	br	입력 값을 받기 위한 버퍼 함수 선언
int	N	사용하고자 하는 N개의 회의
ArrayList<Meeting>	meetingList	시작시간과 종료시간을 입력받아 Meeting 클래스를 선언하여 ArrayList에 객체를 저장
Meeting(클래스) - Comparable		시작시간과 종료시간을 받고 정렬하기 위한 객체 Comparable(클래스 정렬 인터페이스)인터페이스를 상속받은 Meeting 클래스를 선언하여 회의시간을 정렬하기 위해 compareTo 메서드를 오버라이딩해준다.
String[]	str	값을 입력받아 split 메서드를 통해 공백을 기준으로 문자열을 쪼개 시작시간, 종료시간을 저장하는 임시 String 배열
greedy(ArrayList<Meeting> list)	greedy	Meeting 클래스 타입의 ArrayList를 받아 조건에 따라 총 회의 수를 카운트하여 총 회의 수(cnt)를 리턴한다.

 

📌 진행

❗️Comparable 인터페이스(클래스 정렬 인터페이스)를 상속받는 Meeting 클래스를 구현한다.

class Meeting implements Comparable<Meeting>{
    int startTime = 0;
    int endTime = 0;

    Meeting(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }
    @Override
    public int compareTo(Meeting o) {
        if (this.endTime == o.endTime) return this.startTime - o.startTime;
        return this.endTime - o.endTime;
    }
}

Meeting 클래스는 객체 생성 시 회의의 시작시간(startTime)과 종료시간(endTime)을 매개변수로 받는다. Comparable 인터페이스를 상속받기 위해서는 compareTo 메서드를 오버라이드(Override) 해줘야한다. compareTo 메서드를 재정의하면 해당 return 값에 따라 Collections.sort() 메서드가 Meeting 객체가 담긴 ArrayList를 정렬해준다.

 

return this.endTime - o.endTime 

→ 종료시간을 기준으로 오름차순으로 정렬해준다.

 

if(this.endtime == o.endTime) return this.startTime - o.startTime;

→ 비교 객체들의 종료시간이 서로 같다면 시작시간을 기준으로 오름차순으로 정렬한다.

 

❗️반복문을 통해 입력받은 값으로 객체를 선언해 meetingList에 담아준다. 

        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            meetingList.add(new Meeting(Integer.parseInt(str[0]), Integer.parseInt(str[1])));
        }
        
        Collections.sort(meetingList);

 

❗️총 회의 횟수를 리턴하는 greedy 메서드를 구현해준다.

    public static int greedy(ArrayList<Meeting> list) {
        int cnt = 0;
        int startTime = 0;
        int endTime = 0;

        for (Meeting meeting: list) {
            if(endTime <= meeting.startTime) {
                startTime = meeting.startTime;
                endTime = meeting.endTime;
                cnt++;
            }
        }
        return cnt;
    }

• Meeting 클래스 타입의 ArrayList를 매개변수로 받는다.
• forEach(Enhanced for)문을 사용해 Meeting 객체(meeting)를 가져온다.
• 회의시간이 안겹치는 경우(endTime <= meeting.startTime)현 회의 시작 시간과 종료 시간은 바뀐 회의 시간이 되고 회의 수를 카운트 해준다. (cnt)

 

❗️return 된 총 회의 수(greedy(meetingList)) 값을 출력

 

📌 전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Meeting> meetingList = new ArrayList<>();
        String [] str = {};


        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            meetingList.add(new Meeting(Integer.parseInt(str[0]), Integer.parseInt(str[1])));
        }


        Collections.sort(meetingList);

        for (Meeting me:meetingList) {
            System.out.println("start = " + me.startTime+", end = "+me.endTime);
        }

        int ans = greedy(meetingList);
        System.out.println(ans);
    }

    public static int greedy(ArrayList<Meeting> list) {
        int cnt = 0;
        int startTime = 0;
        int endTime = 0;

        for (Meeting meeting: list) {
            if(endTime <= meeting.startTime) {
                startTime = meeting.startTime;
                endTime = meeting.endTime;
                cnt++;
            }
        }
        return cnt;
    }
}

class Meeting implements Comparable<Meeting>{
    int startTime = 0;
    int endTime = 0;

    Meeting(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }
    @Override
    public int compareTo(Meeting o) {
        if (this.endTime == o.endTime) return this.startTime - o.startTime;
        return this.endTime - o.endTime;
    }
}

 

📌 참조

그리디 알고리즘(Greedy Algorithm) : 욕심쟁이 알고리즘(클릭)