요격 시스템(13분)

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

구현 아이디어 5분 구현 8분

풀이

1. 일단 targets 배열을 s 값을 기준으로 오름차순 정렬한다.
2. for문을 돌며 이전 미사일의 끝 값보다 지금 미사일의 시작 값이 더 작으면 합치는데, 끝 값은 더 작은 값으로 갱신한다.
3. 이전 미사일의 끝 값보다 지금 미사일의 시작 값이 같거나 크면 answer을 하나 더하고 이전 미사일의 시작 값과 끝 값을 갱신한다.

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

using namespace std;

struct Data
{
    int s, e;
    Data(int a, int b)
    {
        s = a;
        e = b;
    }
    bool operator<(const Data& b) const
    {
        return s < b.s;
    }
};

int solution(vector<vector<int>> targets) {
    int answer = 1;
    
    vector<Data> V;
    
    int N = targets.size();
    for(int i = 0; i < N; ++i)
    {
        int s = targets[i][0];
        int e = targets[i][1];
        V.push_back(Data(s, e));
    }
    
    sort(V.begin(), V.end());
    
    int prevS = V[0].s;
    int prevE = V[0].e;
    
    for(int i = 1; i < V.size(); ++i)
    {
        int curS = V[i].s;
        int curE = V[i].e;
        
        if(prevE > curS)
        {
            prevE = min(prevE, curE);
        }
        else
        {
            ++answer;
            prevS = curS;
            prevE = curE;
        }
    }
    
    return answer;
}

---

다른 사람의 풀이를 공부하여 끝 값을 정렬해서 푼 풀이. comp 함수를 사용해서 sort를 더 깔끔하게 만들었다.

풀이

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

using namespace std;

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

int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    sort(targets.begin(), targets.end(), comp);
    
    int e = -1;
    for(auto& target : targets)
    {
        // target의 시작 값이 이전 값의 끝 값보다 같거나 크다면.
        if(target[0] >= e)
        {
            e = target[1];
            ++answer;
        }
    }
    
    return answer;
}