4. 프로그래머스 - 요격 시스템

문제 설명  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. 최대한 적은 수의 수직선으로 모든 수평선을 관통해야하는 문제    2. 모든 수평선을 시작점을 기준으로 정렬한다.  3. 시작은 가장 앞에 있는 수평선을 현재 선으로 지정하고 시작  4. 다음 수평선과 현재 수평선이 겹치는 부분이 있고 다음 수평선의 끝점이 더 작다면 현재 선을 다음 수평선으로 변경  5. 다음과 현재 수평선이 겹치는 부분이 없을 경우 수직선 1개 추가하고 다음 선을 현재 선으로 변경     (현재 선의 끝점과 다음 선의 시작점의 좌표가 같다면 겹치지 않는것)   6. 반복하면 필요 최소 수직선이 나옴

    public class Point
    {
        public Point(int start, int end)
        {
            this.start = start;
            this.end = end;
        }

        public int start;
        public int end;
    }

    public int solution(int[,] targets)
    {
        int max = targets.Length / 2;
        List<Point> pointList = new List<Point>();

        for(int i = 0; i < max; ++i)
        {
            pointList.Add(new Point(targets[i,0], targets[i, 1]));
        }

        //정렬
        int cal = 0;
        pointList.Sort((item1,item2) =>
        {
            cal = item1.start.CompareTo(item2.start);
            if (cal == 0)
            {
                cal = item1.end.CompareTo(item2.end);
            }

            return cal;
        });

        Point savePt = pointList[0];
        Point curPt;
        int count = 1;

        //체크
        for (int i = 1; i < pointList.Count; ++i)
        {
            curPt = pointList[i];

            //저장된 마지막점이 현재의 시작점보다 뒤에 있을 경우(같은 라인을 사용하고 있는 경우)
            if (savePt.end > curPt.start)
            {
                //저장된 마지막점이 현재의 마지막 점보다 뒤에 있을 경우(기준을 바꿔야할 타이밍)
                if(savePt.end > curPt.end)
                {
                    savePt = curPt;
                }
            }
            //중첩되지 않음
            else
            {
                ++count;
                savePt = curPt;
            }
        }

        return count;
    }

 

여러모로 날로 먹은 문제, 글을 보면서 뭐 이리 말이 길어 싶어서 슬쩍 밑에 설명 그림을 봤는데 바로 유레카 해버리고

어떻게 검색을 해야 할까 고민하다가 정렬해 보라는 힌트에 유레카 해버려서 풀어버린 문제