JArchive 프로그래밍 일기

문제 링크 

첫 번째 풀이 : 시작점을 기준으로 정렬했다.

end_point는 차가 나가는 지점을 저장한다. 

answer 는 감시카메라 개수 변수다. 

차 2대가 {1, 3} {4, 5} 이 순서로 오는 경우

두 차는 겹치지 않으니까 answer++ 로 카메라를 추가해줘야 한다. 

그리고 마지막 차가 나가는 지점은 5가 된다. end_point = r[1];

차 2대가 {1, 6} { 2, 3} 이 순서로 오는 경우

두 번째 차가 빨리 나가버린다. 

이 때는 종료지점이 더 짧은 3으로 end_point를 갱신해줘야 한다. 

차 2대가 {1, 6} { 2, 3} {4, 9} 이 순서로 오는 경우

 {1, 6} { 2, 3} 을 감시하는 카메라 말고, 하나 더 필요하다. 

새로운 차 { 4, 9 }를 감시하려면,  이미 감시한 {1, 6} 이 아니라, {2, 3}과 {4, 9}가 겹치는지를 확인해야 한다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> routes) {
  int answer = 1; // 차가 1대 이상이니까 카메라는 최소 개수 1
  int end_point = routes[0][1]; // 현재 차가 나가는 지점

  sort(routes.begin(), routes.end());
  for(auto r : routes){ // end_point: 현재 차,  r: 다음 차
    if(end_point < r[0]){ // 현재 차와 다음 차가 겹치지 않으면, 카메라 추가
      answer++;
      end_point = r[1]; // 다음 차 나가는 지점으로 갱신
    }

    // 현재 차가 end_point 보다 먼저 나간다면? 나가는 지점을 현재 차로 수정  
    if(r[1] <= end_point) end_point = r[1];
  }
  return answer;
}

두 번째 풀이 : 종료 지점으로 정렬했다. 

여기서는 감시카메라 개수를 0 으로 초기화 한다. 

마지막 지점은  end_point = -30001 ; 가장 작은 수로 초기화 한다. 

따라서 자동차가 1개 여도, 감시카메라 개수를 1 추가한다. 

주어진 배열

종료 지점이 빠른 순으로 정렬하면 아래와 같다. 

자동차 1개일 때는 첫 번째 자동차만 감시하면 된다.

여기서 감시카메라 개수는 1이다. 이때 end_point = -15 

두 번째 자동차 시작점은 -18이다.  end_point 보다 작다. 따라서 감시카메라를 추가하지 않아도 된다. 

세 번째 자동차의 시작점은 -14 니까 end_point 보다 크다. 감시카메라를 추가해야한다. 

이 때 end_point는 세 번째 자동차의 종료지점으로 갱신한다. 

end_point 는 자동차가 겹치는 마지막 지점으로 이해하면 수월하다. 

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

bool cmp(vector<int> &a, vector<int> &b) {
  return a[1] < b[1]; // 종료 지점 기준으로 정렬
}

int solution(vector<vector<int>> routes) {
  int answer = 0;
  sort(routes.begin(), routes.end(), cmp);
  int end_point = -30001; // 초기값은 가장 작은 수

  for(auto r : routes){ // end_point: 현재 차,  r: 다음 차
    if(end_point < r[0]){
      answer++;
      end_point = r[1];
    }
  }
  return answer;
}