[ 프로그래머스 / LV2 / 파이썬 Python ] 요격 시스템

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

프로그래머스

 

코드

---

def solution(targets):
    answer = 1
    targets.sort()
    end = targets[0][1]
    for s,e in targets[1:]:
        if s >= end: # 떨어진 경우
            answer += 1
            end = e
        elif e <= end: # 포함된 경우
            end = e
    return answer

 

풀이

---

언뜻 보면 복잡한 과정을 거쳐야 할 것 같지만 앞과 뒤 둘 중 하나의 기준만 잡으면 해결할 수 있는 문제였다.

아래는 문제의 아이디어를 생각해내면서 적은 주석이다.

'''
1. 현재 요격가능한 범위의 가장 짧은 범위의 끝을 저장 - end
2. end와 겹치는 범위가 있는 것들을 모두 한번에 처리
3. 정렬한 배열에서는 다음 미사일이 범위를 벗어나면 그 뒤의 미사일들도 범위를 벗어남.
'''

위의 아이디어를 다시 정리해보면 다음과 같다.

• target배열을 정렬해서 맨 왼쪽의 가장 짧은 것들부터 탐색한다.
• 범위가 겹치는 미사일들을 한번에 처리하기 위해 겹치는 미사일 중 가장 짧은 범위의 마지막을 저장한다. ->  end
• target이 정렬이 되어 있기 때문에 시작부분은 반드시 이전 미사일보다 크거나 같다.
• end보다 더 짧은 범위의 미사일이 있으면 그 미사일로 범위를 좁힌다.
• 만약 시작구간이 end를 벗어나면 새로운 겹침범위를 생성해야 한다.
• 이전 겹침범위의 미사일들은 요격처리하고 end를 새롭게 갱신한다.