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

문제

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

접근 방법

최근 배운 그리디, 정렬을 이용했다.
1. 끝 점을 기준으로 내림차순 정렬을 했다.
2. 처음부터 시작한다. (시작점 저장)
3. 현재 끝점보다 이전 시작점 + 0.1 이 크거나 같으면 다른 묶음으로 분류한다. 시작점을 갱신해준다.
4. 반복한다.
5. 주의 :

• 시작점의 범위가 좁아지는 것을 생각하여, 이전 시작점보다 현재 시작점이 클 경우 새로 갱신해준다.
• 구간이 폐구간( [] )가 아니라 개구간( () )임에 유의한다.

테스트케이스, 반례 모음

• [[3, 6], [2, 4], [5, 6], [1, 3]]
  • 2
• [[0, 4], [5, 10], [6, 8], [8, 9]]
  • 3
• [[1, 2], [2, 3], [1, 3], [3, 4], [4, 5], [3, 5]]
  • 4
• [[1, 5], [2, 6], [3, 7], [4, 8], [4, 5]]
  • 1
• [[2, 4], [3, 5], [4, 6], [1, 3]]
  • 2
• [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [1, 6]]
  • 5
• [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
  • 5
• [[1, 3], [1, 3], [1, 3], [1, 3]]
  • 1
• [[0, 4], [1, 2], [1, 3], [3, 4]]
  • 2
• [[0, 4], [0, 1], [2, 3]]
  • 2
• [[3, 6], [2, 4], [5, 6], [1, 3]]
  • 2

풀이

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

using namespace std;

bool compare(vector<int> a, vector<int> b)
{
    if (a[1] == b[1])
        return a[0] > b[0];
    return a[1] > b[1];
}
int solution(vector<vector<int>> targets) {
    int answer = 1;
    
    // 끝으로 정렬
    sort(targets.begin(), targets.end(), compare);
    
    // 시작점
    int startX = targets[0][0]; 

    for(int i=1; i<targets.size(); i++)
    {

        // 이전 시작점이 다음 끝보다 크거나 같은 경우
        if (startX + 0.1 > targets[i][1])
        {
            // 다른 묶음으로 분류
            startX = targets[i][0];
            answer++;
        }
        else if (startX < targets[i][0])
        {
            startX = targets[i][0];
        }
    }
    
    return answer;
}

// Time: 0.01 ms, Memory: 4.19 MB

정리

테케는 맞았는데 개구간이랑 갱신을 반례하면서 깨달았다..