[프로그래머스/Python] 요격 시스템

 

 

문제

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

 

[문제 설명]

​

A나라가 B나라를 침공했다.

요격 시스템이 있지만 비용이 있어서 요격 횟수를 최소로 해야하기 때문에 미사일의 요격을 최소로 하는 횟수를 구하는 문제다.

 

이때 상대방의 미사일이 날아오는 구간을 알 수 있기 때문에 요격 시스템으로 상대방의 미사일의 구간사이에 요격을 하면 요격에 성공한 것으로 간주한다.

 

 

 

풀이

 

[풀이]

 

먼저 미사일들의 s 값을 기준으로 정렬을 했다.

(이전에 요격에 성공한 미사일의 구간과 이번에 요격할 미사일의 구간이 겹치는지를 확인하기 위해서)

​

s를 기준으로 정렬을 했기 때문에 현재 구간의 s부분이 이전 구간의 e보다 크거나 같은지 비교한다.

크거나 같을 경우 요격할 수 있는 구간을 벗어났기 때문에 새로 요격을 해야한다.

새로 요격을 할 경우 요격수를 1 늘려주고 ed를 현재 미사일의 e로 바꿔준다.

​

만약 현재 미사일의 s가 이전에 요격한 미사일의 e보다 작다면 이 미사일도 요격이 가능하다.

​

그리고 현재 미사일의 e가 이전에 요격한 미사일의 e보다 작은지 비교해야한다.

만약 이전에 요격한 미사일의 e보다 작다면, 현재 미사일의 e보다 작은 구간을 요격해야하므로 e값을 현재 미사일의 e값으로 새로 갱신해 준다.

 

 

Code

 

 

def solution(targets):
    answer = 0
    sortedList = sorted(targets, key = lambda x: x[0])
    ed=sortedList[0][1]
    cnt=1
    for i in range(len(sortedList)):  
        nowSt=sortedList[i][0]
        if ed>sortedList[i][1]:
            ed=sortedList[i][1]
        if nowSt>=ed: # st부분이 끝보다 크거나 같으면 cnt +1
            ed=sortedList[i][1]
            cnt+=1
    return cnt

 

---

 

처음에 코드를 약간 이상하게 작성해서 생각보다 시간이 오래 걸렸다;;

 

이런 문제는 쉬운데 갑자기 아이디어가 생각안나면 오래 걸릴것 같은 문제...

 

프로그래머스