요격시스템 (-)

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

프로그래머스

문제 : 요격 시스템의 미사일이 폭격 미사일을 쏘아 맞추는 문제로, 폭격 미사일은 개구간 (s,e)로 표현되어 s와 e에서 요격할 수 없다. s와 e사이에서 가장 많이 폭격 함으로써 발사했던 최소한의 요격 미사일 수를 구하는 문제.

 

로직:

1. 폭격 미사일(targets) 범위가 주어지기에 시작 지점을 기준으로 오름차순 정렬한다.

2. 이전의 폭격미사일 시작점(preStart)과 끝점(preEnd) 그리고 현재의 폭격미사일의 시작점(curStart)과 끝점(curEnd)을 구한다.

이전 시작점과 현재시작점 그리고 이전 끝점과 현재 시작점을 비교조건을 기반으로 폭격 범위를 끝점은 min값, 시작점은 max값 알고리즘을 이용해 좁혀나간다.

3. 폭격범위를 벗어나면 answer를 증가시키고 preEnd , preStart를 curEnd, curStart로 갱신한다.

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

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(),targets.end()); //오름차순 정렬
    int preStart = targets[0][0]; 
    int preEnd = targets[0][1];
    for(int x = 0; x < targets.size(); ++x){
        if(answer==0){ // 첫번째 폭격 미사일은 이전의 폭격미사일로 초기에 설정하기에, 더이상 진행 하지 않고 폭격 카운팅만 하나 증가 
            answer++;
            continue;
        }
        int curStart = targets[x][0]; // 현재 인덱스의 시작
        int curEnd = targets[x][1];  // 현재 인덱스의 끝
        if(preStart <= curStart && preEnd > curStart){ //pre: (0,2)  cur: (1,2)  만일 cur이 (2,n) 이면 이전의 폭격미사일과함께 폭격할 수없음. (0,2)와 (2,n) 개구간 지점에서 함께 요격이 불가. 
            preEnd = min(preEnd, curEnd); // 범위를 좁혀나감 preEnd는 적게
            preStart = max(preStart,curStart); // 범위를 좁혀나감.   preStart는 크게
        }
        else{ // 현재 폭격 미사일이 이전의 폭격미사일과의 같은 폭격 구간이 아니면,
            answer++; // 개별적으로 폭별.
            preEnd = curEnd;  //pre 갱신.
            preStart =curStart;
        }
    }
    return answer;
}

 

 

 

 

 

 

 

 

오름차순 정렬의 기준을 end - start 인덱스가 아닌, start인덱스를 기준으로 정렬.

이전의 start와 end 초기값을 첫 인덱스의 start, end로 설정.

현재의 start값이 이전의 end값보다 작으면 answer++ 

그렇지 않으면 answer를 counting 하지 않는다.

그리디.

 

 

---

 

 

 queue<int> a;
    queue<int> b;
    a.push(5);
    b = a; //복사.
    b = queue<int>(); //https://unluckyjung.github.io/cpp/2020/04/14/Queue_clear/ 
    //queue 클리어함수가 없어서 재생성 또는 q.pop으로 해야됨

---

시간초과 및 3,4번 테스트 실패.

시간초과 이유 myMissile이 해당 요격(나의) 미사일의 범위를 O(N)탐색, 타격미사일이 하나가 있어도 O(N)탐색 

여러 반복문으로 O(N^3) 시간복잡도. 

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//최대 idx갯수 발생하면 queue초기화하여 savingBombIdx에 저장.
// 해당 idx의 targets 삭제.
bool comp(vector<int>& var, vector<int>& tar) {
    int var_dist = var[1] - var[0];
    int tar_dist = tar[1] - tar[0];
    return var_dist < tar_dist;
}

int solution(vector<vector<int>> targets) {
    int answer = 0;
    //범위 작은 순 정렬
    sort(targets.begin(), targets.end(), comp); 
    //작은 범위 기준 (벡터)
    for (int myRocket = 0; myRocket < targets.size(); ++myRocket) {
        if (targets[myRocket].empty())continue;
        answer++;
        int maxi = -1;
        queue<int>savingBombIdx;
        for (int rocket = targets[myRocket][0]; rocket < targets[myRocket][1]; ++rocket) {
            float myMissile = rocket + 0.5f; // 폭격미사일의 개구간에서는 요격미사일이 발사되지 않는다. 0~ 1 폭격미사일이 위치 시 요격미사일은 0과 1제외한 0~1사이에서 발사가능
            queue<int>bomb;
            //그 다음의 큰 범위가 작은 범위의 특정 값에 포함되면 counting.  queue 통해 idx 저장.
                for (int targetMissile = myRocket + 1; targetMissile < targets.size(); ++targetMissile) { // 요격미사일이 target 미사일을 몇개나 때리는지 갯수 파악 및 해당 target idx 저장
                    if (targets[targetMissile].empty())continue;
                    if (targets[targetMissile][0] < myMissile && myMissile < targets[targetMissile][1]) {
                        bomb.push(targetMissile);
                    }
                }
                int bombCounting = bomb.size(); // if에 bomb.size() 직접사용하면 pass가 되는 기이한 현상.
                if (maxi < bombCounting) { // counting이 최대가 되면 해당 타겟미사일 인덱스 저장 및 폭탄 갯수 최댓값 갱신.
                    savingBombIdx = bomb;
                    maxi = bomb.size();
                }
        }
        //나 자신 포함해서 savingBombIdx 지우기
        targets[myRocket].erase(targets[myRocket].begin(),targets[myRocket].end()); //이중벡터의 인덱스를 삭제하고 싶었지만 방법 알지 못하여, 요소의 값들 삭제해서 사이즈를 0으로 만듦. 위 내 자신의 미사일 또는 타겟 미사일 사이즈가 0이면 continue로 진행안되게 예외처리 
        while (!savingBombIdx.empty()) {
            int targetIdx = savingBombIdx.front();
            savingBombIdx.pop();
            targets[targetIdx].erase(targets[targetIdx].begin(), targets[targetIdx].end());
        }
    }
    return answer;
}

int main(void) {
    cout << solution({ {0,500},{500,1000},{0,1},{8,9},{1100,5000000},{5000001,8000000} });
}

 

 

 

 

 

 

진행중 ( 정확성 18.2, 시간초과)

#include<bits/stdc++.h>
using namespace std;
/*
주어진 이중벡터로 endIdx - startIdx= dist가 작은 순으로 오름차순 정렬.

이중 for이용  500,000^2 (시간복잡도)
for문 통해서 각 인덱스 탐색, startIdx 또는 endIdx가 다음 순서의 인덱스들의 startIdx 와 endIdx 내에 포함된다면 (개구간)
checked 배열 활용 -> 완전 동일한 범위의 폭격미사일이 2개 이상있을 수 있다. 일반 배열이 아닌, hash map을 활용.
미리 1중 for이용해서 갯수를 파악해 value에 설정.

요격할 때 마다 key에 찾아가 value 감소. 만일 0이면 이미 폭격한 상태로 pass.


hash로
*/
struct node {
    long long startIdx;
    long long endIdx;
    int checked;
};
unordered_map<int, node> um;
bool comp(vector<int>& var, vector<int>& tar) {
    int var_dist = var[1] - var[0];
    int tar_dist = tar[1] - tar[0];
    return var_dist < tar_dist;
}
void init(const vector<vector<int>>& targets) {
    for (int idx = 0; idx < targets.size(); ++idx) {
        um[idx] = {targets[idx][0], targets[idx][1], 0}; // startIdx, endIdx, checked
    }
}
int solution(vector<vector<int>> targets) {
    sort(targets.begin(), targets.end(), comp);
    init(targets);
    int answer = 0;
    //y : 요격 미사일 인덱스로 간주(사실 폭격미사일 인덱스임 그러나 한번 맞출때 최대한 많은 갯수를 맞추는 쪽으로 가야하니 y의 startIdx, EndIdx 가 x의 범위를 포함하면 x까지도 폭격 가능), x : 폭격 미사일 인덱스
    for (int y = 0; y < targets.size() - 1; ++y) {
        if (um[y].checked == 1) continue;
        answer++;
        um[y].checked = 1;
        int y_startValue = um[y].startIdx;
        int y_endValue = um[y].endIdx;
        for (int x = y + 1; x < targets.size(); ++x) { //x = 0이 아닌 이유 : 이미 앞에 있는 인덱스가 search했기에.
            if (um[x].checked == 1) continue;
            int x_startValue = um[x].startIdx;
            int x_endValue = um[x].endIdx;
            //y가 x의 범위 안에 있으면 x checked = 1 // 
             //폭격미사일은 개구간, 요격 미사일은 실수좌표에서 발사 가능하니 소수점에서도 발사가능,
            if (y_startValue + (y_endValue - y_startValue) <= x_startValue) continue;  // 개구간 조건.
            if (x_startValue + (x_endValue - x_startValue) <= y_startValue)continue; // 개구간 조건. 
            if (y_startValue < x_startValue && y_endValue < x_endValue) {
                um[x].checked = 1;
            }
            else if (y_startValue >= x_startValue && y_endValue <= x_endValue) {
                um[x].checked = 1;
            }
        }
    }
    return answer;
}

int main(void) {
    cout<<solution({ {4,5},{4,8},{10,14},{11,13} ,{5,12},{3, 7},{1, 4} });
}

 

 

 

2차 진행중

#include<bits/stdc++.h>
//주어진 2중벡터 start Val 와 end Val 차이가 작은것부터 순서대로 오름차순 나열.
//while문으로 요격인덱스 기준은 첫번째 인덱스부터 시작, 대상이 되는 폭격  미사일을 거리 조건에 제한을 두어 폭격 여부를 가린다.
// 범위에 들어오면 target 폭격의 인덱스는 pop한다. 하나의 루프가 돌면 counting 1 씩 한다.
using namespace std;
int maxi = -1;
bool comp(vector<int> var, vector<int> tar) {
    return var[1] - var[0] < tar[1] - tar[0];
}
int solution(vector<vector<int>> targets) {
    int answer = 0;
    vector<int>saveIdx;
    //2차원벡터 내 1차원벡터 자체적으로 없애고 싶은데 사이즈 0으로 남아있긴하네.  
    // 아래 테스트해보기.
    // https://www.digitalocean.com/community/tutorials/2d-vectors-in-c-plus-plus   
    sort(targets.begin(), targets.end(), comp);
    int varIdx = 0;
    while (targets.size() != 0) {
        for (int startVal = targets[varIdx][0] + 1; startVal <= targets[varIdx][1]; ++startVal) {
            float myVal = startVal - 0.5;
            vector<int>bombIdx;
            for (int idx = varIdx + 1; idx < targets.size(); ++idx) //폭격 대상 벡터 인덱스.
            {
                int tarVal_s = targets[idx][0];
                int tarVal_e = targets[idx][1];
                if (tarVal_s < myVal && myVal < tarVal_e) {
                    bombIdx.push_back(idx);
                }
            }//
            int bsize = bombIdx.size();
            if (maxi <bsize) {
                maxi = bsize;
                saveIdx = bombIdx;
            }
    
        }
        //Todo 지우기

        targets[varIdx].erase(targets[varIdx].begin(), targets[varIdx].end()); //https://stackoverflow.com/questions/7801210/how-to-erase-element-in-2d-vector
        
        for (int idx = saveIdx[0]; idx < saveIdx.size(); ++idx) {
            targets[idx].erase(targets[idx].begin(), targets[idx].end()); //https://stackoverflow.com/questions/7801210/how-to-erase-element-in-2d-vector
        }
        varIdx += 1;
        answer += 1;
        // Todo: maxi saveIdx값들을 targets 인덱스로하여 지우기.
        //  for(int idx = saveIdx[0]; idx<saveIdx.size();++idx){
        //  targets.erase(idx); // 2차원벡터에 폭격지우기. maxi갱신될때마다.
  
//}
    }
    return answer;
}
//[[4, 5], [4, 8], [10, 14], [11, 13], [5, 12], [3, 7], [1, 4]]
int main(void) {
    cout<< solution({ {4,5},{4,8},{10,14},{11,13},{5,12},{3,7},{1,4} }) <<'\n';
}