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

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

프로그래머스

정답코드

# 2023-06-30
# 2023-07-12
# 복습 횟수:1, 00:30:00, 복습필요:*(세 달 뒤 쯤 복습하면 될듯 - 그때도 맞으면 끝)
def solution(targets: list):
    answer = 0
    targets.sort(key=lambda x: x[1])
    end = 0

    for target in targets:
        if target[0] >= end:
            answer += 1
            end = target[1]


    return answer

solution([[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]])

 

풀이

1. 두번째 x를 기준으로 오름차순으로 정렬합니다.

2. 만약 그 다음 것의 첫번째 x가 기준으로 삼았던 것의 두번째 x보다 크거나 같다면 

쏴야하므로 answer += 1을 하고 end를 초기화해줍니다.

 

2번이 가능한 이유:

 

case1의 경우 target[0] >= end 이므로 총알 한번에 두 개를 모두 관통할 방법이 없습니다. 따라서 += 1이 됩니다.

반면 case2의 경우 target[0] <end 이므로 이는 반드시 기존의 것과 겹치는 부분이 있다는 것을 의미합니다. (두번째 x를 기준으로 정렬했으므로) 따라서 이 경우엔 두 개를 모두 관통할 방법이 있으므로 answer += 1 을 하지 않습니다.