[JAVA / 자바] 백준 1931번 - 회의실 배정 (실버 2)

 문제 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용 표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

---

 입력 

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

---

 출력 

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

---

---

 문제 접근 방법 

회의실에 회의를 최대한 많이 넣어야 한다. 그럼 무엇을 따져 이를 알아낼 수 있을까?

 

바로,

입력된 회의의 정보를 종료시간을 기준으로 오름차순으로 정렬한 후 앞에서부터 순서대로 회의 시간이 겹치지 않게 배정해주면 된다.

 

왜? 회의 종료 시간을 기준으로 오름차순 정렬하냐면,

회의실에 회의를 배정해 주려면 앞선 회의가 끝나야 다음 회의를 배정해 줄 수 있다. 이것으로 알 수 있듯이 회의가 끝나는 시간이 중요하다는 뜻이다. 그래서 회의가 끝나는 시간을 기준으로 오름차순 정렬을 한다.

 

위와 같은 이유로 정렬된 배열을 앞에서부터 순차적으로 돌면서 앞선 회의가 끝나는 시간을 저장해 두고 앞선 회의가 끝나고 시작하는 회의를 찾아 다시 회의 끝나는 시간을 최신화해주면서 배정되는 회의의 개수를 카운팅해 그 수를 출력하면 문제는 해결된다.

 

+) 추가적으로 나는 다음을 비교해보고자 한다.

    - 2차원 배열로 정렬

    - 객체를 선언하여 정렬

---

 JAVA 코드 풀이 

1. 2차원 배열

2. 클래스 선언

 코드 실행 결과 

1. 2차원 배열 Ver. 코드 실행 결과

2. 클래스 선언 Ver. 코드 실행 결과

---

 후기 

처음에는 모든 경우의 수를 다 따져봐야만 하는 줄 알았다. 그러나 회의를 배정하려면 앞선 회의가 종료되어야 다음 회의가 진행될 수 있다는 생각이 들었고 위와 같은 논리로 코드를 작성했을 때 최대의 결괏값이 나오게 되었다.

 

그래서 코드를 작성하다가 문득 이런 생각이 들었다. 이걸 2차원 배열로 푸는 것이 효율이 좋을까 아니면 객체를 선언하여 푸는 것이 효율이 좋을까? 그래서 둘 다 코드로 작성해서 실행해 보았더니 2차원 배열로 푸는 것이 시간은 더 빨랐지만 객체를 선언한 것이 메모리 측면에서 효율적이었고 가독성도 좋아졌다고 생각한다. 앞으로 문제를 풀면서 다양한 방법과 새로운 방법을 많이 접하겠지만 그때마다 드는 의문을 바로바로 해결하고 알아가는 것 또한 나에게 값진 경험이라 생각이 든다.

---

 문제 원본 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 알고리즘 분류 

• 그리디 알고리즘
• 정렬