개발/알고리즘
[프로그래머스] 요격 시스템
개발자_티모
2023. 5. 6. 02:01
반응형
[문제 설명]
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))
반응형