[프로그래머스] 요격 시스템 - python

문제 출처 

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

프로그래머스

 

 

문제 풀이 및 코드

 

먼저 범위를 살펴보자.

targets의 길이 <= 500,000 이고 s,e <= 100,000,000 이다. 즉 x좌표를 전부 살펴보면 시간 초과가 발생한다. 또한 targets의 길이가 500,000이니 nlog(n)까지 가능할 것이다. (필자는 O(n)에 끝내려고 고민하다가 오래걸렸음)

 

해당 문제는 sort후에 계산하는 게 유리하다. 기존에 end 포인트 보다 큰 s가 들어온다면 새로운 요격 기기를 설치해야하고, 기존의 end 보다 작은 s가 들어온다면 새로운 end 포인트를 설정해 주어야할 것이다.