[프로그래머스] [C++] 단속 카메라 (set, greedy)

1. 문제

코딩테스트 연습 - 단속카메라 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 단속카메라

 

 

2. greedy

 

이 문제는 set 문제로 생각할 수 있다.

 

겹치는 부분이 생기면 한 set에 있다고 생각하는 것이다.

 

단 이때 set을 형성하는 순서가 중요하다. (그리디 => 제일 가까운 것이랑 set형성)

 

lo 기준 hi기준 으로 적당히 순차적으로 set을 형성하면 된다.

 

 

set(lo, hi) = lo ~ hi 인 범위를 포함하고 있는 원소들의 집합

 

이렇게 함수를 표현하고 나면 이제 set의 size를 리턴하게 하면 문제는 해결된다.

 

 

이때 set 자료구조는 

오버라이딩된 비교연산자를 통해 false 가 나오면

오퍼랜드의 자리를 바꾸어 false가 나오면 같은거로 취급한다.

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>
 
using namespace std;
 
class ca{
public:
    int *lo, *hi;
    ca(int *_lo = nullptr, int *_hi = nullptr): lo{_lo}, hi{_hi} {}
    bool operator < (const ca& c) const {
        if((*c.lo <= *hi && *hi <= *c.hi) || (*c.lo <= *lo && *lo <= *c.hi)){
            *lo = max(*c.lo, *lo);
            *hi = min(*hi, *c.hi);
            return false;
        }
        return *lo > *c.lo;
    }
};
int solution(vector<vector<int>> routes) {
    set<ca> mp;
    sort(routes.begin(), routes.end());
    for (int i = routes.size() -1 ; i >= 0; i--){
        mp.insert(ca(&routes[i][0],&routes[i][1]));
    }
    return mp.size();
}