프로그래머스 2023.08.24 (2Lv 요격 시스템)

프로그래머스

문제

---

문제 설명
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

입출력 예

targets	result
[ [4,5], [4,8], [10,14], [11,13], [5,12], [3,7], [1,4] ]	3

코딩

---

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

using namespace std;

struct tGroup_Info
{
    int x;
    int y;
};

bool Sort(vector<int> _vecA, vector<int> _vecB)
{
    if (_vecA[0] == _vecB[0])
        return _vecA[1] < _vecB[1];

    return _vecA[0] < _vecB[0];
}

int solution(vector<vector<int>> targets) {
    int answer = 0;

    sort(targets.begin(), targets.end(), Sort);
    vector<tGroup_Info> vecGroup;

    int ix = 0;
    int iy = 0;

    for (size_t i = 0; i < targets.size(); ++i)
    {
        ix = targets[i][0];
        iy = targets[i][1];

        // 가장 첫 검사는 바로 집어넣어준다.
        if (vecGroup.size() == 0)
        {
            tGroup_Info tNewGroup;
            tNewGroup.x = ix;
            tNewGroup.y = iy;
            vecGroup.push_back(tNewGroup);
        }
        else
        {
            bool bResult = false;
            for (size_t j = 0; j < vecGroup.size(); ++j)
            {
                // 구간이 교집합일때,
                if (!((iy <= vecGroup[j].x) || (ix >= vecGroup[j].y)))
                {
                    bResult = true;

                    // 그룹 구간 재설정
                    vecGroup[j].x = max(vecGroup[j].x, ix);
                    vecGroup[j].y = min(vecGroup[j].y, iy);

                    break;
                }
            }

            // 현재 존재하는 모든 그룹과 구간이 겹치지 않을 때
            if (!bResult)
            {
                tGroup_Info tNewGroup;
                tNewGroup.x = ix;
                tNewGroup.y = iy;
                vecGroup.push_back(tNewGroup);
            }
        }
    }

    answer = (int)vecGroup.size();

    return answer;
}

제일 처음 Targets의 첫 미사일 범위를 vecGroup에 넣어주고, 이후 Targets를 순회하면서 기존 Group에 존재하는 미사일 범위와 겹치는지 확인하는 방식으로 만들었다. 만약, 이번에 검사하는 미사일 범위가 기존 그룹에 겹치는게 있지 않을 경우 새로 그룹을 추가해주었다.

이렇게 검사를 모두 마친 뒤 vecGroup의 사이즈가 최소 미사일 갯수이므로  정답으로 반환해주었다.

 

처음 코드를 짰을 때 정렬을 하지 않고 했는데, 오답이 많이 나왔다. 정렬을 해주지 않을 경우 그룹이 덜 나뉘거나 더 나뉘는 현상이 발생하기 때문에 Targets에 들어있는 마사일의 시작 지점을 기준으로 오름차순으로 정렬해 준 뒤 검사를 진행하니, 정답이 나왔다.

 

사실 이렇게 정렬을 해주면, 그룹 검사를 복잡하게 할 필요가 없기 때문에 검사 코드를 다시 짜보려한다.

 

 

 

실행 결과

---

<첫 시도 때 코드 결과>