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

[문제 설명]

A나라에서 발사한 미사일의 구간이 (s, e)로 주어지고, B나라는 최소한의 요격 미사일로 A가 날린 미사일을 요격해야 한다.
B가 사용하는 최소한의 미사일을 개수를 찾는 문제다.

 

[해결 방법]

 저는 이 문제를 풀기위해 그리디 알고리즘을 사용했습니다. 그리디 알고리즘을 사용한 이유는 다음과 같습니다. 우리가 원하는 답은 최소한의 요격 미사일 개수 입니다. A가 날린 미사일의 위치를 모두 알 수 있으니, 우리는 미사일의 공통된 구간을 찾아서 요격 미사일을 날려주면 원하는 답을 찾을 수 있습니다.  

 

코드

# Copyright 2023 bae
# 
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
# 
#     http://www.apache.org/licenses/LICENSE-2.0
# 
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

def solution(targets):
    answer = 0
    targets.sort()
    
    start_y = -1
    
    for x, y in targets:
        if x < start_y:
            if y < start_y:
                start_y = y
        else:
            answer += 1
            start_y = y
            
    return answer


if __name__ == "__main__":
    target = [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]	
    result = 3
    
    print(solution(target))