일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 스파르타내일배움캠프TIL
- 장고
- 롤
- python
- java
- github
- 알고리즘
- Django
- 탐욕알고리즘
- Riot
- 그리디
- API
- 코딩테스트준비
- 자바
- 백준
- sort
- drf
- programmers
- 파이썬
- 라이엇
- 그리디알고리즘
- lol
- 프로그래머스
- greedy
- SQL
- 코딩테스트
- 스파르타내일배움캠프
- git
- 내일배움캠프
- 리그오브레전드
- Today
- Total
Lina's Toolbox
[Greedy] 백준 - 회의실 배정 본문
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
예제 입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
예제 출력 1
4
힌트
- (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
- 그리디 알고리즘
풀이
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 첫 번째 줄에서 회의의 수 N 입력받기
int N = scanner.nextInt();
List<int[]> meetings = new ArrayList<>();
// N개의 회의 정보를 입력받기
for (int i = 0; i < N; i++) {
int start = scanner.nextInt(); // 회의 시작 시간
int end = scanner.nextInt(); // 회의 종료 시간
meetings.add(new int[] {start, end});
}
// 회의 시간을 종료 시간을 기준으로 정렬
Collections.sort(meetings, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[1] != b[1]) {
return Integer.compare(a[1], b[1]); // 종료 시간 기준 정렬
}
return Integer.compare(a[0], b[0]); // 시작 시간이 같으면 시작 시간 기준 정렬
}
});
int count = 0; // 선택한 회의 수
int lastEndTime = -1; // 마지막 회의의 종료 시간 초기화
// 회의 선택
for (int[] meeting : meetings) {
int start = meeting[0];
int end = meeting[1];
// 현재 회의의 시작 시간이 마지막 회의의 종료 시간보다 크거나 같다면
if (start >= lastEndTime) {
count++; // 회의 수 증가
lastEndTime = end; // 종료 시간 업데이트
}
}
System.out.println(count); // 결과 출력
scanner.close();
}
}
처음엔, 회의 시간이 짧은 순서대로 정렬하여 회의를 배치해야하는 줄 알고 풀었다가 틀렸다.
회의 시간을 기준으로 정렬하는 것은 잘못된 접근이다.
회의 시간이 짧은 것을 먼저 선택하는 것이 아니라, 종료 시간을 기준으로 정렬한 후 회의를 선택해야 한다.
짧은 회의 시간 기준으로 정렬하는 경우, 종료시간으로 정렬하여 회의를 배치하는 것보다, 겹치는 회의가 발생할 가능성이 더 높아진다.
예를 들어
(1, 4), (3, 5), (4, 5), (5, 7)라는 회의가 있다면,
종료 시간 기준으로 정렬하면:
- (1, 4)
- (3, 5)
- (4, 5)
- (5, 7)
이 경우 종료 시간으로 정렬하면, (1, 4)를 선택한 후 (4, 5)와 (5, 7)로 3개의 회의를 배치할 수 있다.
하지만, 회의 시간 순으로 선택하여 (3, 5)를 먼저 선택하면, (1, 4)와 (4, 5)를 선택할 수 없고, (3,5)와 (5,7) 2개만 배치할 수 있어 더 비효율적인 것 이다.
따라서, 이 문제에서는
종료 시간 기준으로 회의를 정렬하는 것이 효율적인 선택입니다. 이는 최대 회의 수를 보장하기 위한 최적의 전략이다!
문제 링크
https://www.acmicpc.net/problem/1931
그리디 알고리즘을 학습하면서, 리스트나 배열로 주어지는 경우,
먼저 적절한 기준으로 정렬을 한 후 접근하는 것이 아주 중요하다는 점을 깨달았는데,
이 문제를 풀면서, 논리적으로 올바른 정렬 기준을 찾는 것이 그리디 알고리즘에서 가장 중요한 것 같다고 느꼈다.
'문제 풀이 > 백준' 카테고리의 다른 글
[Greedy] 백준 - 주유소 (1) | 2024.09.27 |
---|---|
[Greedy] 백준 - 잃어버린 괄호 (1) | 2024.09.27 |
[Greedy] 백준 - 동전 0 (1) | 2024.09.26 |
[Greedy] 백준 - ATM (0) | 2024.09.26 |
[Greedy] 백준 - 거스름돈 (0) | 2024.09.24 |