C# 요격 시스템 - 정렬 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/181188

 

 

나의 풀이

public int solution(int[,] targets) 
{
    var list = new List<(int, int)>();
    for(int i = 0; i < targets.GetLength(0); ++i)
        list.Add((targets[i, 0], targets[i, 1]));

    list = list.OrderBy(o => o.Item1).ToList();

    int answer = 0;
    int tail = int.MaxValue;
    foreach((int start, int end) point in list)
    {
        if(point.end < tail)
        {
            tail = point.end;
            continue;
        }

        if(point.start >= tail) // 같이 요격될 수 없음
        {
            ++answer;
            tail = point.end;
        }
    }

    return answer + 1; // 마지막 그룹은 요격안했으니 + 1
}

범위가 작다면 배열을 선언하고 전부 넣은 다음에 그리디로 큰것부터 제거하는 것을 생각해 볼 수 있으나

좌표 제한사항이 굉장히 큰 편.

 

정렬을 하고 O(N)의 복잡도로 풀어야 하는 문제.  

 

시작점을 기준으로 정렬하고서 하나씩 꺼내면서, 맨 처음에 꺼낸 미사일과 같이 요격될 수 없을 때까지 미사일을 꺼낸다. 

같이 요격될 수 없다면 앞 그룹은 한번 요격한다음, 반복한다.