프로그래머스: 단속카메라⭐⭐⭐

체감 난이도 : ⭐⭐ 유형 : 그리디 걸린 시간: 1시간 5분

🧐 문제

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routes	return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

---

✏️ 나의 풀이

#include <bits/stdc++.h>

using namespace std;

// 진입 시점 기준 오름차순 정렬
// 진입 시점이 같다면, 진출 시점 기준 내림차순 정렬
bool comp(vector<int> a, vector<int> b) {
  if(a[0] == b[0]) {
    return a[1] > b[1];
  }
  return a[0] < b[0];
}

int solution(vector<vector<int>> routes) {
  int answer = 0;
  sort(routes.begin(), routes.end(), comp);

  vector<int> border; // 겹치는 부분
  for(auto route : routes) {
    if(border.empty() || border[1] < route[0]) {
      border = route;
      answer++;
    } else {
      border[0] = max(border[0], route[0]);
      border[1] = min(border[1], route[1]);
    }
  }

  return answer;
}

차량마다 카메라가 설치되어야 하는 구간이 존재한다.
즉, 차량 i는 routes[i][0]에서 routes[i][1] 사이에 적어도 하나의 카메라가 있어야 한다.
그러므로 최대한 겹치는 부분을 모아주면 된다.

• 차량을 진입 시점을 기준으로 오름차순 정렬한다.
• 만약 진입 시점이 같다면, 진출 시점을 기준으로 내림차순 정렬한다.
• routes 벡터를 순회하며 겹치는 구간이라면 border 업데이트
• 겹치지 않는다면, border를 초기화시키며 answer++;

코드는 잘 작동하지만, 내가 짠 코드에는 필요없는 부분들이 있다.

• 진입 시점이 같다면, 진출 시점 기준 내림차순 정렬할 필요가 없다.
• border[0] 부분이 사용되지 않는다.

---

✔️ 다른 사람의 풀이

#include <bits/stdc++.h>

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;
    int limit = -30001;
    sort(routes.begin(), routes.end(), cmp);
    for(int i = 0; i < routes.size(); i++){
        if(limit < routes[i][0]){
            answer++;
            limit = routes[i][1];
        }
    }
    return answer;
}

이 사람은 진입 시점이 아닌, 진출 시점을 기준으로 오름차순 정렬하였다.

• limit 변수를 진출 시점(구간의 끝점)으로 둔다.
• limit 변수가 다음 구간의 진입 이전에 위치한다면, → 겹치지 않는다는 것을 의미한다.
• 그 외의 상황(limit ≥ 구간.start)이라면, → 이미 설치된 카메라가 이 구간을 커버하고 있다는 것을 의미한다.
• limit 변수를 새로운 진출 시점으로 업데이트 후, answer++;

Programmers 카테고리 내 다른 글 보러가기