새로운 차 { 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 추가한다.
주어진 배열
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]
종료 지점이 빠른 순으로 정렬하면 아래와 같다.
[[-20,-15], [-18,-13], [-14,-5], [-5,-3]]
자동차 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;
}
#include <bits/stdc++.h>
using namespace std;
bool cmp(vector<int> &a, vector<int> &b){
return a[2] < b[2];
}
int get_parent(vector<int> &parent, int x){
// 부모노드가 자신이라면 자신을 리턴
if(parent[x] == x) return x;
// 부모노드가 자신이 아니라면, 최상위 부모 찾기
return parent[x] = get_parent(parent, parent[x]);
}
void union_parent(vector<int> &parent, int a, int b){
a = get_parent(parent, a);
b = get_parent(parent, b);
// 작은 노드쪽의 부모로 병합
a < b ? parent[b] = a : parent[a] = b;
}
bool find(vector<int> &parent, int a, int b){
a = get_parent(parent, a);
b = get_parent(parent, b);
return a == b; // 비교 내용을 리턴, 사이클 방지용
}
// 크루스칼 알고리즘 : 비용이 적은 순으로 costs 정렬
int solution(int n, vector<vector<int>> costs) {
int answer = 0, maxNum = 0;
sort(costs.begin(), costs.end(), cmp);
for(auto c : costs) if(maxNum < c[1]) maxNum = c[1];
vector<int> parent; // i번째 노드의 부모노드를 저장하는 parent 벡터
for(int i = 0; i <= maxNum; i++) parent.push_back(i);
for(auto c : costs){
// 두 개의 부모 노드가 다르다면 (사이클 없다면)
if(!find(parent, c[0], c[1])){
answer += c[2]; // 결과에 가중치 추가
union_parent(parent, c[0], c[1]); // 부모노드 병합
}
}
return answer;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n = 4;
vector<vector<int>> costs{{0,1,1}, {0,2,2}, {1,2,5}, {1,3,1}, {2,3,8}};
cout << solution(n, costs);
return 0;
}
