알고리즘 풀이 - 백준 1931(회의실 배정, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

회의실이 1개일 때, N개 회의에 대한 사용표를 만들고자 한다. 회의의 시작/종료 시간이 주어질 때, 겹치지 않도록 회의실을 쓰는 최대 회의의 수를 구하는 문제

 

 

2. 풀이

 

이 문제는 대표적인 그리디 알고리즘으로 해결 가능한 활동 선택(Action Selection) 문제이다.

최대한 많은 회의를 수행하기 위해서는 끝나는 시간을 기준으로 정렬을 수행하면 된다. 왜냐하면, 무조건 일찍 끝나는 회의를 우선 수행한 뒤, 다음 회의들을 수행하면 가장 최대의 회의를 진행할 수 있기 때문이다.

즉, 시간이 겹치지만 않는다면 무조건 더 빠르게 끝나는 회의를 우선적으로 수행하고 이후에 가능한 회의들 중 가장 빠르게 종료되는 회의 순서로 지속 수행하면 된다.

 

그런데 이에 추가로 종료 시간을 기준으로 하되 종료 시간이 같다면 시작 시간이 더 빠른 것을 앞에 두어야 한다.

그 이유는 시작시간과 끝 시간이 같을 수 있기 때문이다. 예를 들어, 아래와 같은 경우가 있을 수 있다.

시작시간	1	2	4	4	5
종료시간	2	4	4	5	5

 

이것을 좀 더 이해가 쉽게 그림으로 알아보자.

 

이 문제의 정답은 a1 ~ a5까지 모든 회의를 다 수행하는 것이다.

그런데 입력 순서에 따라 종료 시간을 기준으로 정렬을 한다면 아래와 같은 경우가 있을 수 있다.

순서 : a1 - a2 - a3 - a5 - a4

 

즉, a5가 a4보다 먼저 오게 되는 경우이다. 종료 시간이 같은데, 시작 시간을 기준으로는 정렬하지 않으면 위와 같은 현상이 발생할 수 있게 된다.

이런 현상이 발생하는 이유는, 시작/종료 시간이 같은 경우가 있기 때문이다. 그러면, 시작 시간이 더 늦었음에도 종료시간이 같다는 이유로 더 앞에 오는 현상이 있을 수 있다.

 

따라서, 이 문제는 종료 시간이 같다면 시작 시간이 더 이른 것을 우선 해야 한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int n = Integer.parseInt(br.readLine());
        
        // 회의 정보를 저장한다.
        PriorityQueue<Meeting> pq = new PriorityQueue<>();
        Meeting[] list = new Meeting[n];
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            long start = Long.parseLong(st.nextToken());
            long end = Long.parseLong(st.nextToken());
            
            pq.offer(new Meeting(start, end));
        }
        
        // 그리디 알고리즘을 통해 정답을 구하여 출력한다.
        int ans = greedy(pq);
        System.out.println(ans);
        br.close();
    }
    
    private static int greedy(PriorityQueue<Meeting> pq){
        // 반환할 회의 수
        int ans = 0;
        
        // 현재 시간
        long time = 0;
        while(!pq.isEmpty()){
            Meeting meeting = pq.poll();
            // 회의 시작 시간이 현재 시간과 같거나 이후인 경우
            if(time <= meeting.start){
                // 수행 가능한 회의 수를 추가
                ans++;
                
                // 시간을 회의의 종료 시간으로 업데이트
                time = meeting.end;
            }
        }
        return ans;
    }
}

// 회의 정보를 저장하는 Class
// Comparable을 구현하여 정렬 방식을 지정한다.
// 종료 시간을 기준으로 오름차순 정렬하되, 종료 시간이 같다면 시작 시간이 더 빠른 것을 우선으로 하였다.
class Meeting implements Comparable<Meeting>{
    long start;
    long end;
    public Meeting(long start, long end){
        this.start=start;
        this.end=end;
    }
    
    @Override
    public int compareTo(Meeting m){
        if(this.end == m.end){
            return Long.compare(this.start, m.start);
        }
        return Long.compare(this.end, m.end);
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.