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

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

using namespace std;

bool sortCompare(vector<int> a, vector<int> b)
{
    return a[1] < b[1];
}

int solution(vector<vector<int>> targets) 
{
    int answer = 0;
    int end = 0;
    
    sort(targets.begin(),targets.end(), sortCompare);
    
    for(int i = 0; i < targets.size(); i++)
    {
        if(targets[i][0] >= end)
        {
            answer++;
            end = targets[i][1];
        }
    }
    
    return answer;
}

 

풀이

1. 끝지점이 작은순으로 정렬해준다.

2. 끝지점과 다음 시작점이 맞닿았다면 해당 끝지점으로 바꿔준다.

 

 

0부터 시작해서 첫번째에 1번 범위가 잡히고(1) 2번의 시작점과 1번의 끝지점이 같거나 크므로 다시 변경(2) 2번의 끝지점과 5번의 시작점이 같거나 크므로 다시변경(3)

위 방법으로 총 3번의 겹치는 구간이 완성된다.

 

느낀점

범위를 잡는 문제는 종종풀었던 것 같은데 확실하게 이해하고 가야될 것 같다. 끝지점을 잡는게 포인트인 것 같다.

 

 

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

프로그래머스