문제

BOJ 2457, 공주님의 정원

핵심

• 입력의 크기가 $10^5$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 꽃들의 피는 날과 지는 날이 주어질 때, 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 하는 꽃의 최소 개수를 구해야 한다. 11월 30일까지 피어야 한다면 12월 1일부터 지는 꽃을 선택해야 한다.
• 처음 문제에 접근할 때 3월이면 31일, 4월이면 30일, 5월이면 31 처럼 달에 맞는 일수를 정확하게 파싱해야 한다고 생각해서 복잡했지만, 주어진 입력에서 잘못된 입력은 없으므로 아래처럼 간단하게 파싱할 수 있다.

for (int i = 0; i < n; ++i) {
	int sm, sd, em, ed;
	cin >> sm >> sd >> em >> ed;
	flowers.push_back({sm * 100 + sd, em * 100 + ed});
}

• 현재 시점에서 피어 있는 꽃 중 가장 오랫동안 피는 꽃을 선택하면 가장 적은 꽃을 선택할 수 있다는 명제로 문제에 접근한다. 3월 1일부터 시작하여 가장 오랫동안 피는 꽃을 선택하고 해당 꽃이 지는 시점을 기준으로 다시 가장 오랫동안 피는 꽃을 선택하면 가장 적은 꽃을 선택할 수 있다.
• 처음 문제에 접근할 때는 우선순위 큐를 사용하여 가장 오랫동안 피는 꽃 기준으로 정렬하고, 해당 시점에 필 수 있는 꽃을 찾을 때까지 오랫동안 피는 꽃들을 잠시 다른 곳에 이동시켰는데, 불필요한 삽입과 삭제가 많아서 시간초과가 발생하였다. 가지치기를 고려하지 않고 시간복잡도를 생각해보면 최악의 경우 $n \times logn(삭제) \times n \times logn(삽입)$이 일어날 수 있다.
• 효율적으로 접근하기 위해 가장 일찍 피는 꽃들을 기준으로 정렬하고, 해당 시점에 꽃이 필 수 있다면 가장 오래 피는 꽃을 찾도록 로직을 수정하였다.

개선

코드

시간복잡도

• $O(N\times logN)$

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> flowers;
    for (int i = 0; i < n; ++i) {
        int sm, sd, em, ed;
        cin >> sm >> sd >> em >> ed;
        flowers.push_back({sm * 100 + sd, em * 100 + ed});
    }
    sort(flowers.begin(), flowers.end());
    int st = 301;
    int idx = 0;
    int ans = 0;
    while (st < 1201) {
        int liveDays = 0;
        while (idx < n && flowers[idx].first <= st) {
            liveDays = max(liveDays, flowers[idx].second);
            idx++;
        }
        if (liveDays == 0) {
			ans = 0;
			break;
        }
        st = liveDays;
		++ans;
    }
    cout << ans;
}

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<int[]> flowers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int[] nums = new int[2];
            nums[0] = a * 100 + b;
            nums[1] = c * 100 + d;
            flowers.add(nums);
        }
        flowers.sort((a, b) -> Integer.compare(a[0], b[0]));
        int st = 301;
        int idx = 0;
        int ans = 0;
        while (st < 1201) {
            int liveDays = 0;
            while (idx < n && flowers.get(idx)[0] <= st) {
                liveDays = Math.max(liveDays, flowers.get(idx)[1]);
                ++idx;
            }
            if (liveDays == 0) {
                ans = 0;
                break;
            }
            st = liveDays;
            ++ans;
        }
        System.out.println(ans);
        br.close();
    }
}