[프로그래머스] 요격 시스템(C++)

요격시스템 181188

➡️ 풀어놓고 업로드 안한 밀린 문제들은 어떻게 ㅎ ㅐ야하나. . . ((한숨 . .

🏵 문제 설명

---

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 함수를 완성해 주세요.

🛳 제한사항

---

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

📹 풀이

---

일단 이 문제는 왜 Lv2인가 라는 의문이 드는 문제이다.
약간 백준에 회의실 배정(1931) 과 유사한 문제라고 생각했다.
따라서 Greedy 한 문제구나 라고 생각했다. << 아님 말구 . .

1. targets 벡터 배열을 정렬한다.
2. 정렬된 targets 벡터를 탐색하며 범위(rangeMin, rangeMax)를 비교한다.
3. 현재의 범위 (s, e) 에서 s 가 rangeMax 보다 작은 경우 포함된다고 하고, rangeMin, rangeMax 의 값을 재정의 한다.
   • rangeMin 의 경우 s 와 비교하였을 때 더 큰 값으로 지정
   • rangeMax 의 경우 e 와 비교하였을 때 더 작은 값으로 지정
4. 현재의 범위가 (rangeMin, rangeMax) 에서 벗어나는 경우 새로 범위를 지정하고 answer 의 값을 키운다.

그림으로 표현하면 위와 같다 . . . 참조 하면 된다! !

⏰ 코드

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

bool compare(vector<int> a, vector<int>b) {
    if (a[0] < b[0]) return true;
    else if (a[0] == b[0]) {
        if (a[1] < b[1]) return true;
        else return false;
    }
    else return false;
}

int solution(vector<vector<int>> targets) {
    int answer = 0;
    int rangeMin, rangeMax;
    
    sort(targets.begin(), targets.end(), compare);
    rangeMin = targets[0][0]; rangeMax = targets[0][1];
    
    for (int i = 1; i < targets.size(); i++) {
        if (targets[i][0] < rangeMax) {
            rangeMin = max(rangeMin, targets[i][0]);
            rangeMax = min(rangeMax, targets[i][1]);
        }
        else {
            answer += 1;
            rangeMin = targets[i][0];
            rangeMax = targets[i][1];
        }
    }
    return answer + 1;
}

🎙 어려웠던 점

처음으로 없었다 ! (┐「ε:)