[프로그래머스] 181188. 요격시스템 | 정렬 | 파이썬, 소스코드, 정답

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

---

문제요약

주황선이 미사일, 파란선이 요격

x좌표와 평행하게 날라오는 미사일을 요격해야함

x좌표에서 요격을 쏘면 y좌표와 평행하게 날라가고 해당 x좌표에 존재하는 모든 미사일을 요격할 수 있음

미사일을 모두 요격하는데 필요한 요격미사일의 최소개수를 구해야함

---

문제 조건

미사일의 좌표는 (s, e)로 표현. s는 미사일의 왼쪽 끝 좌표, e는 미사일의 오른쪽 끝 좌표.

s와 e에서는 미사일을 요격할 수 없음. 요격미사일은 실수인 x좌표에서도 발사 가능.

입력으로 targets가 주어짐. targets는 미사일의 좌표 리스트, [[s, e]] (s와 e는 정수)

1 <= len(targets) <= 500,000, 0 <= s < e <= 100,000,000

---

시행착오

처음에 갈피를 잡지 못했음

무조건 O(NlogN)으로 풀어야 하니까 완전탐색 절대안되고 그리디로 풀어야 하나... 고민하다가

다른분 풀이를 보고 정렬문제라는 힌트를 얻음

s를 기준으로 오름차순으로도 정렬해보고 e를 기준으로 내림차순으로도 정렬해본 결과

e를 기준으로 내림차순으로 푸는게 가장 깔끔하다는 결론을 내림.

---

문제풀이 아이디어

1. e를 기준으로 내림차순정렬

2. 미사일끼리 겹치는 구간을 overlapped 변수에 저장, 총 요격 미사일 개수를 answer에 저장

3. 다음 미사일과 겹치면 overlapped 갱신, 안겹치면 answer++, overlapped 초기화

4. 좌표가 각각 (s1, e1), (s2, e2)인 두개의 미사일이 존재할 때 e1>e2이고 s2 >= e1이면 두 미사일은 겹치지 않음

5. 두 미사일이 겹친다고 가정하면 겹치는 부분은 (max(s1, s2), min(e1, e2)임

 

---

소스코드

def solution(targets):
    answer = 1

    targets.sort(key=lambda x: -x[1])
    overlapped = [targets[0][0], targets[0][1]]

    for i in range(len(targets) - 1):
        if overlapped[0] >= targets[i+1][1]:
            answer += 1
            overlapped = [targets[i+1][0], targets[i+1][1]]
        else:
            overlapped = [max(overlapped[0], targets[i+1][0]), min(overlapped[1], targets[i+1][1])]

    return answer