프로그래머스-단속카메라

문제 링크

1. 문제 접근 과정🧐

1. 시작 지점이나 도착 지점에 카메라를 설치하여도 만나는 것으로 인정되는 것을 파악
2. 도착 지점을 기준으로 정렬
3. 도착 지점에 카메라를 설치하고 해당 지점이 다음 루트의 사이라면 유지
4. 다음 루트의 사이가 아니라면 카메라의 설치를 다음 루트의 도착으로 옮기고 개수를 늘리는 방식을 해결

2. 시행착오🤯

• 처음에 루트의 시작과 끝을 따로 관리하여 활성화된 루트가 모두 포함되는 것을 보면 되지 않을까 해서 구현하다가 쉽지 않아 이건 아니다 싶었다.
• 오답 코드

#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int solution(vector<vector<int>> routes) {
	int answer = 0;
	vector<pair<int,int>> r;
	for(int i = 0; i < routes.size(); i++){ 
		int s = routes[i][0], e = routes[i][1]; 
		r.push_back({s, i + 1});
        r.push_back({e, -(i + 1)});
	} 
	sort(r.begin(), r.end(), [](pair<int,int> p1, pai<int,int> p2){
		 if(p1.first == p2.first) return p1.second > p2.second;
         return p1.first < p2.first;
   	}); 
	// () - (1) - (1, 3) - (3) - (2, 3) - (2) - (2, 4) - (4) - () 이런 식으로 활성화 관리?
	return answer; 
}

3. 개선한 코드😄

• 문제 접근 방식에서 말했듯이 해당 문제는 그리디하게 끝지점을 다음 루트와 비교하여 갱신하면 해결
  • 처음에 설치하고 시작하므로 초기값은 1로 해야 한다.
    
• 정답 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> routes) {
    vector<pair<int,int>> r;
    for(int i = 0; i < routes.size(); i++){
        int s = routes[i][0], e = routes[i][1];
        r.push_back({s, e});
    }
    sort(r.begin(), r.end(), [](pair<int,int> p1, pair<int,int> p2){
        if(p1.second == p2.second) return p1.first < p2.first;
        return p1.second < p2.second;
    });
    int camera = r[0].second;
    int answer = 1;
    for(auto p : r){
        if(camera < p.first){
            answer++;
            camera = p.second;
        }
    }
    return answer;
}

4. 회고💭

• 입출력 예시나 조건을 보면 힌트를 얻을 수 있었는데 생각하지 못했다.
• 다양한 문제를 풀어보면서 그리디하게 푸는 방식이 되는지 판단하는 요령이 필요하다.