문제
오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.
총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)
이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.
- 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
- 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다.
출력
첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.
풀이
이 문제는 그리디 문제입니다.
조건을 간략하게 정리하면 결국 다음과 같습니다.
- 3월 1일부터 11월 30일까지 피어있는 꽃은 1개 이상 존재해야 한다.
- 심는 꽃의 개수는 최소로 한다.
1번의 조건만 고려한다면 단순한 문제이지만, 심는 꽃의 개수가 최소여야 한다는 점이 문제를 풀 때 막혔던 부분입니다.
꽃을 순회하는 과정에서 이전에 심은 꽃의 지는 날짜를 latestDate 라고 하겠습니다. 꽃을 순회하면서 꽃이 계속 피어있는 상태로 심기 위해서는, 현재 꽃의 피는 날짜가 latestDate보다 앞에 있어야 합니다.
하지만 이때 latestDate내에 심을 수 있는 꽃은 여러 개 있을 수 있습니다. 이때 심는 꽃의 개수가 최소로 하려면 어떻게 해야할까요??
심을 수 있는 여러 개의 꽃 중에서 지는 날짜가 제일 뒤에 있는 것을 고르면 됩니다. 마찬가지로, 심을 수 있지만 꽃의 지는 날짜가 latestDate 보다 빠르다면 굳이 심을 필요가 없습니다.
그런데 꽃을 순회하는 과정에서 피는 날짜와 지는 날짜가 엉켜있으면 뒤에 있는 꽃이 현재 이후로 가장 빨리 피는 꽃임을 보장할 수 없습니다. 따라서 꽃을 다음 우선순위로 정렬해야 합니다.
- 꽃이 피는 날짜 순
- 꽃이 지는 날짜 순
만약 다음과 같이 입력이 주어졌을 때, 정렬 결과는 다음과 같습니다.
// 정렬 전
6 10 12 10
5 15 8 31
1 1 6 30
1 1 5 31
// 정렬 후
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10
위 과정을 코드로 나타내면 다음과 같습니다.
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<Flower> flowers = new ArrayList<>();
for (int i = 0; i < n; i++) {
int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int startDate = 100 * input[0] + input[1];
int endDate = 100 * input[2] + input[3];
flowers.add(new Flower(startDate, endDate));
}
Collections.sort(flowers);
int count = 0;
int latestDate = 301;
int idx = 0;
while (idx < n) {
// 꽃이 비어있는 기간이 생기거나, 꽃이 있어야 하는 기간이 종료된 경우
if (latestDate < flowers.get(idx).startDate || latestDate > 1130) {
break;
}
// 해당 꽃을 심어야 하는 경우
if (flowers.get(idx).startDate <= latestDate && latestDate < flowers.get(idx).endDate) {
int maxEndDate = flowers.get(idx).endDate;
// 심을 수 있는 꽃 중에서 지는 날짜가 가장 늦은 꽃을 탐색한다.
while (idx + 1 < n && latestDate >= flowers.get(idx + 1).startDate) {
idx++;
// 심을 수는 있지만, 지는 날짜는 더 빠를 수도 있음
maxEndDate = Math.max(maxEndDate, flowers.get(idx).endDate);
}
count++;
latestDate = maxEndDate;
}
idx++;
}
if (latestDate <= 1130) {
System.out.println(0);
return;
}
System.out.println(count);
}
static class Flower implements Comparable<Flower> {
int startDate;
int endDate;
public Flower(int startDate, int endDate) {
this.startDate = startDate;
this.endDate = endDate;
}
@Override
public int compareTo(Flower o) {
if (this.startDate == o.startDate) {
return this.endDate - o.endDate;
}
return this.startDate - o.startDate;
}
}
참고
'알고리즘' 카테고리의 다른 글
| 배열의 구간 변화 빠르게 구하기 (0) | 2024.12.27 |
|---|