문제

Programmers, 단속카메라

핵심

• 입력의 크기가 $10^4$이라 대략 $O(N^2)$ 이하 알고리즘을 사용한다.
• 고속도로를 이동하는 차량의 경로가 주어질 때 모든 차량을 감시할 수 있도록 단속 카메라를 설치하는 문제이다. 단속 카메라 최소 개수를 구해야 한다.
• 고속도로 진입점과 진출점이 주어지는데 이중 한 곳에는 반드시 카메라가 설치되어야 해당 차량을 감시할 수 있다. 카메라를 진출점에 설치하면 다른 차량의 경로를 보고 감시할 수 있는지 쉽게 확인할 수 있다.[[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 해당 예시에서 첫 번째 차량 -15에 카메라를 설치했다면 3번째 차량은 경로 안에 카메라가 있으므로 감시할 수 있다.
• 모든 차량의 경로를 방문하면서 감시할 수 없다면 카메라를 설치한다. 이를 효율적으로 처리하기 위해 진출점을 기준으로 오름차순 정렬하여 자신보다 진출점이 큰 경로에 대해서만 검사한다. (해당 지점의 진출점보다 작은 진출점은 감시할 수 없기 때문이다)

++ans;						// 카메라 설치
int point = routes[i][1];
for (int j = i + 1; j < n; ++j) {
	if (routes[j][0] <= point && routes[j][1] >= point)
    	isVis[j] = true;	// 다음 차량 경로도 감시 영역에 포함
}

개선

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

int solution(vector<vector<int>> routes) {
    int n = routes.size();
    sort(routes.begin(), routes.end(), [](auto& a, auto& b) {
        return a[1] < b[1];
    });
    vector<bool> isVis(n, false);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (isVis[i])
            continue;
        ++ans;
        isVis[i] = true;
        int point = routes[i][1];
        for (int j = i + 1; j < n; ++j) {
            if (routes[j][0] <= point && routes[j][1] >= point)
                isVis[j] = true;
        }
    }
    return ans;
}

• 해당 코드로 통과해서 다른 사람의 풀이를 봤더니 반복문 하나로 풀었다. 시간 차이가 얼마나 될까 싶어서 돌려봤는데 위의 코드보다 느리다. 그런데 이중 반복문으로 감시 영역을 계산하는 게 아니라 반복문 하나로 마지막 카메라 위치보다 해당 경로의 진입점이 크다면 건너뛰는 방식으로 구현한 게 인상깊었다. 위 코드에 반영하니 조금 더 빨라졌다.
  

코드

시간복잡도

• $O(N\times log_2N)$

C++

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

int solution(vector<vector<int>> routes) {
    sort(routes.begin(), routes.end(), [](auto& a, auto& b) {
        return a[1] < b[1];
    });
    int ans = 0;
    int last = -1e9;
    for (auto& e : routes) {
        if (last < e[0]) {
            ++ans;
            last = e[1];
        }
    }
    return ans;
}

Java

import java.util.Arrays;

class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));
        int ans = 0;
        int last = -100000;
        for (var e : routes) {
            if (last < e[0]) {
                ++ans;
                last = e[1];
            }
        }
        return ans;
    }
}