[프로그래머스 코딩테스트] python 요격시스템

문제

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

프로그래머스

미사일 최소 개수 구하기
#A(폭격)는 x축에 평행한 직선(s,e)
#B(요격)는 y축에 평행한 직선(x값, float)으로 A에 해당하는 것 모두 관통가능 
## 단 s,e 점은 해당x

범위

targets=[1,500000]
s,e=[0,100000000]

 

풀이

1. 정의

구해야 하는 선의 개수 : lines

겹치는 구간 : overlaps

 

2. targets의 시작값이 낮은 순서대로 정렬

 

3. 겹치는 구간 정의

overlaps(e)는 targets의 한 구간의 시작점(s)보다 크면 overlaps를 새로 정의

s는 가장 큰 수, e는 가장 작은 수가 겹치게 됨

 

4. 겹치지 않는 구간 정의

새로운 s,e가 overlaps가 되면서 lines +1

def solution(targets):
    lines, overlaps = 0, {'s':0, 'e':0}
    target = sorted(targets)
    for s, e in target:
        #겹치는 부분
        if s<overlaps['e']:
            overlaps['s']=max(s, overlaps['s'])
            overlaps['e']=min(e, overlaps['e'])
            
        #안겹치는 부분
        else:
            overlaps['s']=s
            overlaps['e']=e
            lines+=1

    return lines