lv2) 요격시스템

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

프로그래머스

 

 

코드

#include <string>
#include <vector>
#include<algorithm>
#include <iostream>
using namespace std;

/*
1. targets 오름차순 정렬
2. start지점과 end지점을 이전과 현재를 비교해 범위 좁혀나가기, 범위에 없으면 answer++
*/
int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(), targets.end());
    int prevStart = targets[0][0];
    int prevEnd = targets[0][1];
    for(int idx = 0; idx < targets.size();++idx){
        int curStart = targets[idx][0];
        int curEnd = targets[idx][1];
        if(answer == 0){
            answer++; //시작지점 폭격 전제.
            continue;
        }
        if(prevStart <= curStart && prevEnd > curStart){ // 타격 범위 좁혀나가기
            prevStart = max(prevStart, curStart);
            prevEnd = min(prevEnd, curEnd);
        }
        else{ // 타격범위에서 벗어날 경우 answer++(타격 카운팅) 및 다음 타격 범위로 초기화
            answer++;
            prevStart = curStart;
            prevEnd = curEnd;
        }
        
    }
    
    return answer;
}

풀이 설명 ( 못풀었다면 못푼이유 )

1. 타겟의 요소들을 오름차순 정렬 후
2. 첫 시작은 타격을 가했다는 전제하에 시작한다. 그리고 그 타격의 범위를 정하고자

이전 인덱스와 현재 인덱스를 비교하며 타격 범위를 좁혀나간다.

1. 만일 현재 시작점이 이전 끝점 보다 클 경우 (개구간 허용) 이전의 타격범위에 벗어났기에 다시 타격을 가한다(answer++) 그리고 타격 범위 갱신을 위해 이전 시작점과 끝점을 현재 시작점과 끝점으로 변경한다.