요격 시스템

문제 설명

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

풀이

public class MissileInterceptor
{
    public static int Solution(int[,] targets)
    {
        List<Missile> missiles = new List<Missile>();
        
        //입력된 미사일 제원 초기화
        for (int i = 0; i < targets.GetLength(0); i++)
        {
            Missile newMissile = new Missile(targets[i, 0], targets[i, 1]);
            missiles.Add(newMissile);
        }
        
        //요격 시도 횟수를 카운팅
        int tryCount = 0;
        //미사일을 끝나는 지점이 빠른 순서로 정렬
        missiles = missiles.OrderBy(m => m.End).ThenBy(m => m.Start).ToList();
        //이전에 요격을 시도한 지점을 저장
        int lastShootPoint = int.MinValue;

        foreach (var missile in missiles)
        {
            //현재 미사일의 시작 위치가 이전에 요격을 시도한 지점보다 크거나 같다면
            // = 이전 요격 위치로는 현재 미사일의 구간을 커버할 수 없음
            if (missile.Start >= lastShootPoint)
            {
                tryCount++; // 새로운 요격기 필요
                lastShootPoint = missile.End;
            }
        }

        return tryCount;
    }
}

class Missile
{
    public readonly int Start;
    public readonly int End;

    public Missile(int start, int end)
    {
        Start = start;
        End = end;
    }
}

Missile 클래스

class Missile
{
    public readonly int Start;
    public readonly int End;

    public Missile(int start, int end)
    {
        Start = start;
        End = end;
    }
}

• 폭격 미사일로 해당 미사일의 시작지점과 끝 지점을 입력하여 객체를 생성

초기 구상

실패 전략 : 가장 많은 미사일이 겹치는 지점 선택

A (0,9), B (1,5), C (6,10)
■ ■ ■ ■ ■ ■ ■ ■ ■ □
□ ■ ■ ■ ■ □ □ □ □ □
□ □ □ □ □ □ ■ ■ ■ ■ 
1 2 2 2 2 1 2 2 2 2
2개가 겹치는 칸 중에서 1에 요격 지점을 설치
→ A와 B 미사일 제거
□ □ □ □ □ □ □ □ □ □
□ □ □ □ □ □ □ □ □ □
□ □ □ □ □ □ ■ ■ ■ ■ 
0 0 0 0 0 0 1 1 1 1
6에 요격 지점 설치
→ C 미사일 제거

• 해당 방식을 사용해 Dictionary<int,int>로 field를 구성해 겹치는 지점을 찾아 가장 많은 미사일이 겹치는 지점에서부터 요격해가며 최적의 값을 찾고자 했으나
  지나치게 복잡도가 높아지는 문제가 발생
• 끝나는 지점으로 정렬하여 요격 지점을 찾는 새로운 방식을 학습
  

초기화

        List<Missile> missiles = new List<Missile>();
        
        //입력된 미사일 제원 초기화
        for (int i = 0; i < targets.GetLength(0); i++)
        {
            Missile newMissile = new Missile(targets[i, 0], targets[i, 1]);
            missiles.Add(newMissile);
        }

• 입력된 (s, e)를 기준으로 Missile 객체를 생성하고 missiles 리스트를 통해 관리

정렬

        //미사일을 끝나는 지점이 빠른 순서로 정렬
        missiles = missiles.OrderBy(m => m.End).ThenBy(m => m.Start).ToList();

• 미사일을 끝나는 지점이 빠른 순서로 정렬

  끝나는 지점이 빠른 순서로 정렬하는 이유

  (1,2), (1,4), (2,4) 이렇게 3개의 미사일이 있다고 가정

  첫번째 요소의 끝나는 지점에 요격 지점 설치

  현재 요격 지점 = 2
  요격 가능 미사일 : (1,2), (1,4)
  요격 불가능 미사일 : (2,4)

  만약 (1,2)을 기준으로 요격 지점을 설정하지 않고 그 이후 미사일을 기준으로 하면
  해당 미사일을 요격하지 못함

요격 위치 지정

        foreach (var missile in missiles)
        {
            //현재 미사일의 시작 위치가 이전에 요격을 시도한 지점보다 크거나 같다면
            // = 이전 요격 위치로는 현재 미사일의 구간을 커버할 수 없음
            if (missile.Start >= lastShootPoint)
            {
                tryCount++; // 새로운 요격기 필요
                lastShootPoint = missile.End;
            }
        }

• Missile 객체 리스트를 순회하며 해당 미사일의 시작 위치가 이전 요격 지점보다 뒤에 있다면 현재 요격 위치로는 해당 미사일을 요격할 수 없으므로 해당 미사일의 끝지점으로 요격 위치를 새로 지정

  	i) 시작 지점이 현재 요격 지점보다 앞에 있는 경우 → 격추 가능
  	ii) 시작 지점이 현재 요격 지점보다 뒤에 있는 경우 → 해당 미사일의 끝지점으로 격추 위치 추가추가

해당 방식을 사용해 모든 미사일을 격추할 수 있도록 함