[프로그래머스 Lv.2] 요격 시스템

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

어떤 자료구조에 닮아서 알고리즘을 적용할까 고민을 했지만 떠오르지 않았다.

 

그래서 그리디로 접근해보기로 했다.

 

---

끝점 기준 정렬 + 그리디

 

왜 끝점 기준인가?

 

끝점이 가장 빠른 구간부터 처리하면서, 끝점 직전에서 요격하면

• 해당 구간을 확실히 요격하면서
• 겹치는 다른 구간들도 최대한 많이 커버할 수 있음

시작점 기준으로 정렬하면 "어디서 쏴야 할지" 결정이 애매해짐.

 

방법

1. 끝점 기준 오름차순 정렬
2. 첫 번째 구간의 끝점 직전에서 요격 (요격 횟수 = 1)
3. 나머지 구간 순회:
   • 현재 요격 지점이 구간 안에 있으면 → 이미 요격됨, 패스
   • 구간 밖이면 → 새로 요격, 끝점 직전으로 갱신

예시: [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]

 

정렬 후

[1,4], [4,5], [3,7], [4,8], [5,12], [11,13], [10,14]

결과

 

[1,4]	-	-	요격 cnt=4
[4,5]	4	X	요격 cnt=5
[3,7]	5	O	패스
[4,8]	5	O	패스
[5,12]	5	X	요격 cnt=12
[11,13]	12	O	패스
[10,14]	12	O	패스

---

전체코드

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

using namespace std;

bool compare(const vector<int>& a, const vector<int>& b) {
    if (a[1] < b[1]) {
        return true;
    } else {
        return false;
    }
}

int solution(vector<vector<int>> targets) {
    int answer = 1;
    
    sort(targets.begin(), targets.end(), compare);
    
    int cnt = targets[0][1];
    for(int i=1; i<targets.size();i++) {
        // cout << cnt << "\n";
        if (cnt <= targets[i][0]) {
            cnt = targets[i][1];
            answer++;
        } else {
            continue;
        }
    }
    
    return answer;
}