프로그래머스[Lv.2] - 요격 시스템

문제

제한 사항을 보고 target의 범위와 개수가 많다는 것을 보고 완전 탐색은 불가능하다고 생각했다.

모든 target을 처리해야 하기 때문에 정렬한 후 그리디로 처리해도 될 것이라 판단했다.

 

문제 설명

A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.

A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.

A 나라와 B 나라가 싸우고 있는 이 세계는 2차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.

각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

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

프로그래머스

---

 

 

 

 

 

 

제한 사항

• 1 ≤ targets의 길이 ≤ 500,000
• targets의 각 행은 [s,e] 형태입니다.
  • 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
  • 0 ≤ s < e ≤ 100,000,000

 

---

 

 

 

 

 

 

풀이

하나의 target을 처리한다고 가정했을 때, 이 target이 요격되려면 무조건 e보다 적은 곳에서 처리해야 한다.

즉, e보다 작은 모든것을 같이 처리하면 된다.

이는 정렬이 된 상황에서만 적용되는 논리이다. 따라서, 우선적으로 정렬을 수행한다.

class target {
public:
    target(int a, int b) : s(a), e(b){}
    
    bool operator< (const target& rhs) 
    {
        if(e == rhs.getE())
        {
            return s < rhs.getS();
        }
        return e < rhs.getE();
    }
    
    int getS() const { return s; }
    int getE() const { return e; }
    
    void print()
    {
        cout << "s: " << s << " e: " << e << "\n";
    }
    
private:
    int s,e;    
};

데이터 관리를 편하게 하기위해 class를 제작했고 정렬기준을 설정했다. (e를 오름차순으로, 같다면 s를 비교)

vector<target> dots;
    
for(auto t : targets)
{
    dots.push_back(target(t[0], t[1]));
}

std::sort(dots.begin(), dots.end());

 

 

정렬한 후, e가 가장 작은 target을 기준으로 설정한 후 그 target의 e보다 작은 지점에서 시작하는 traget은 넘긴다. (같이 처리 가능)

e보다 늦게 시작되는 target이 나오면 answer를 증가시킨 후 기준을 새로 설정한다.

이 작업을 끝까지 진행한 후, 마지막까지 유지하던 기준을 마지막에 한 번 더 더해주면 끝이다. 

int end = dots[0].getE();
for(int i = 1; i < dots.size(); i++)
{
    if(end <= dots[i].getS())
    {
        // 포함되지 않음
        answer++;
        end = dots[i].getE();
    }
}

answer++;

 

---

 

 

 

 

 

전체 코드

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

using namespace std;

class target {
public:
    target(int a, int b) : s(a), e(b){}
    
    bool operator< (const target& rhs) 
    {
        if(e == rhs.getE())
        {
            return s < rhs.getS();
        }
        return e < rhs.getE();
    }
    
    int getS() const { return s; }
    int getE() const { return e; }
    
    void print()
    {
        cout << "s: " << s << " e: " << e << "\n";
    }
    
private:
    int s,e;    
};

int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    vector<target> dots;
    
    for(auto t : targets)
    {
        dots.push_back(target(t[0], t[1]));
    }
    
    std::sort(dots.begin(), dots.end());
    
    int end = dots[0].getE();
    for(int i = 1; i < dots.size(); i++)
    {
        if(end <= dots[i].getS())
        {
            // 포함되지 않음
            answer++;
            end = dots[i].getE();
        }
    }
    
    answer++;
    
    return answer;
}

---