백준 : 회의실배정 (1931)

*** 본 풀이는 java언어를 사용하였습니다. ***

문제 보러가기

 

풀이

회의실 사용시간과 끝나는 시간의 회의들을 그래프로 나타내면 다음과 같다.

 

우리가 원하는 것은 최대 사용할 수 있는 회의의 개수를 구하는 것이다.

최대한 많은 회의의 개수를 구하는 방법은 다음과 같이 구할 수 있다.

1. 회의가 끝나는 시간별로 오름차순 정렬
2. 현재 회의의 끝나는 시간과 다음 회의의 시작 시간을 비교
3. 다음 회의의 시작 시간이 더 크다면 최대 사용할 수 있는 회의 개수 1 증가

 

회의가 끝나는 시간별로 오름차순 정렬되어 있으니

3번을 통과한다면 그 시간에서 나올 수 있는 최대 회의 개수가 되기 때문

주의할 점은 회의가 끝나는 시간이 같을 경우는 회의 시작 시간을 비교 해 정렬해야 한다.

회의는 Conference 객체로 분리했다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());
        List<Conference> conferences = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            int[] tokens = Arrays.stream(br.readLine().split(" "))
                                 .mapToInt(Integer::parseInt)
                                 .toArray();
            conferences.add(new Conference(tokens[0], tokens[1]));
        }
        System.out.println(Solution.solution(conferences));
    }
}

class Solution {
    public static int solution(List<Conference> conferences) {
        conferences.sort((o1, o2) -> {
            if (o1.getEndTime() == o2.getEndTime()) {
                return o1.getStartTime() - o2.getStartTime();
            }
            return o1.getEndTime() - o2.getEndTime();
        });
        int result = 1;
        int endPoint = conferences.get(0).getEndTime();
        for (int i = 1; i < conferences.size(); i++) {
            Conference conference = conferences.get(i);
            if (conference.getStartTime() >= endPoint) {
                endPoint = conference.getEndTime();
                result++;
            }
        }
        return result;
    }
}

class Conference {
    private int startTime;
    private int endTime;

    public Conference(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    public int getStartTime() {
        return startTime;
    }

    public int getEndTime() {
        return endTime;
    }

    @Override
    public String toString() {
        return "Conference{" +
                "startTime=" + startTime +
                ", endTime=" + endTime +
                '}';
    }
}

 

회고

회의가 끝나는 순으로 오름차순 정렬을 하면 된다는 생각을 했다면 쉽게 풀었을 문제였다.

회의가 끝나는 시간이 같을 경우는 회의의 시작시간 순으로 정렬했어야 했는데

그 부분은 생각하지 못해서 테스트 실패를 했다..

다음에는 한번에 통과하도록 좀 더 생각하고 코딩해야지