코딩도장

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

targets은 공격당하는범위들이다. 요격미사일을 최소로 쏴서 없애야 한다.

공격범위는 0보다 크다 s<e

일단 targets을 작은 순서로 sort에서 앞에서 부터 겹치는 범위를 찾아서 뒤로가다가 겹치는 범위가 없어지면 새로운 미사일을 준비했다. 

def solution(targets):
    answer = 0
    targets.sort()
    rs=0
    re=0
    cnt = 0
    s=[]
    for i,p in enumerate(targets):
        if(i == 0):
            s = p
            continue
        rs = max(s[0],p[0])
        re = min(s[1], p[1])
        if rs>=re:
            if s[0] < s[1]:
                cnt += 1
            s = p
        else:
            s = [rs,re]
    if s[0] < s[1]:
        cnt += 1
    answer = cnt
    return answer

a =[[0, 4], [1, 2], [1, 3], [3, 4]] #2
a = [[0, 4], [0, 1], [2, 3]] #2
#a = [[0,0],[0,0]] #0
solution(a)

sort(key=lamda x:x[1])을 이용해서 끝을 이용해서 정렬했다.

def solution(targets):
    answer = 0
    targets.sort(key=lambda x:x[1])
    answer = 0
    end = -1  # 마지막으로 요격한 미사일의 x좌표

    for s, e in targets:
        if s >= end:  # 이전에 요격한 미사일로는 현재 미사일을 요격할 수 없는 경우
            answer += 1
            end = e  # 현재 미사일을 요격함으로써 끝나는 지점을 업데이트

    return answer