요격시스템 c++ (그리디, 중복 구간 문제)

문제 링크

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

프로그래머스

 

문제 설명 및 풀이

문제의 요점은 최대한 적은 요격을 사용해 미사일을 전부 제거하는 것이다. 하지만 단순히 최대한 많은 미사일이 겹치는 지점을 우선으로 차례로 제거해나가면 된다(그리디).

이에 한발 더가서, 어차피 모든 미사일은 제거되야하기 때문에, 앞에서부터 순차적으로 가장 많이 겹치는 지점에서 제거해나가도 올바르게 정답을 찾을 수 있다.

 

해설

겹치는 미사일을 찾아나갈 때,  시작점 기준으로 정렬을 해주면 뒤에오는 미사일들은 시작점이 현재 미사일 보다 같거나 큰 미사일이다.  (현재 미사일의 시작점 <= 다음 미사일의 시작점)

따라서,  '다음 미사일의 시작점 <  현재 미사일의 끝점' 만 성립하면 겹치는 것이다. ( 선분 교차 공식)

a 미사일과 b 미사일을 겹친 뒤, 다음 미사일인 c 도 a,b와 겹치려면,   a미사일과 b 미사일의 중복구간과 겹쳐야한다.

 

a,b의 중복구간 ==  ( [a,b 시작점 중 최대,   a,b 끝점 중 최소  )  이다.

어차피 뒤에오는 미사일은 항상 시작점이 더 앞에있기에 갱신할 필요없이 b 미사일의 시작점으로 잡으면 되고, 끝점의 경우, Min연산을 통해 a,b 미사일 중 끝점이 더 작은 것으로 갱신하면 중복구간을 구할 수 있다.

 

이렇게 계속해서 중복 구간을 구하다가, 중복구간이 발생하지 않는다면, 해당 미사일은 겹치지 못하는 것이니 종료하면 a미사일을 없애는 모든 지점의 경우의 수 중, 가장 많은 중복이 발생하는 지점을 찾을 수 있다.

 

정답 코드

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

bool cmp(vector<int> a, vector<int> b){  //시작이 빠른 순서로
    if(a[0]!=b[0])return a[0]<b[0];
   // return a[1]<b[1];
}

//vector<int> point_num[500001];// 각각의 s-1, e-1에서 겹치는 개수를 누적
//위를 벡터의 크기 순으로 정렬하고 위에서부터 제거!

int erase[500001];


//그리디: 시작점이 빠른 순 정렬, 이후 끝지점이 빠른 순 정렬
//이후 앞의 미사일 부터 부터 최대한 많이 겹치도록 미사일을 제거해나간다.

int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(),targets.end(),cmp);
    for(int i=0;i<targets.size();i++){
        int s=targets[i][0],e=targets[i][1];
        if(erase[i])continue;
        answer++;
        erase[i]=1;
        int point=e-1;  
        for(int j=i+1;j<targets.size();j++){
             int ns=targets[j][0],ne=targets[j][1];
            if(ns<e){ //겹치는가? 최대한 많이 겹치는 끝지점까지 늘려나간다
                i=j;// j까지 겹치면서 나가기에, 따로 탐색할 필요 x
                e=min(ne,e);
                erase[j]=1;
            }
            else{
                break; //중요!!! 끝이 빠른 순으로 sort되어있기에 바로 안찾아지면 종료 가능
            }
            
        }
        
        
    }
    
    return answer;
}