[프로그래머스] Lv2. 요격 시스템

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

코드

def solution(targets):
    targets.sort(key=lambda x : x[1])
    now = targets[0]
    answer = 1
    for s, e in targets:
        if now[1] <= s:
            answer += 1
            now = [s,e]
        else:
            continue
    return answer

풀이

• 회의실 배정하는 문제와 비슷하게 풀 수 있다.
• s~e 사이에서 어떤 지점에서 요격하든 해당 미사일을 요격할 수 있다.
• 그래서 우선 커버할 수 있는 범위가 끝나는 지점을 기준으로 오름차순 정렬을 해준다.
• 초깃값으로, 현재 레이저를 쏘는 범위를 now라고 하고, 0번 인덱스로 넣고, answer는 1이다.
• for문으로 미사일을 순회하는데, 이 때 현재 커버할 수 있는 범위의 끝 now[1]보다 미사일 시작 좌표 s가 크거나 같을 경우 요격 미사일을 하나 더 발사해야 하므로 answer을 1 올리고, now 범위를 커버할 수 있는 s, e 값으로 갱신해준다.
• now[1]가 s일 때에도 갱신하도록 포함한 것은 s, e에서는 요격할 수 없기 때문이다.