본문 바로가기

알고리즘

응급환자 발생

Basic 100 · 85번Lv. 2완전 탐색

응급환자 발생

문제 설명

실리콘밸리로 출장을 가는 도중 응급환자가 다수 발생했습니다. 현재 위치는 바다 한 가운데이며, 가장 빠른 시간 내에 환자를 치료할 수 있는 공항으로 이동해야 합니다. 각 공항과의 거리와 그 공항에서 치료할 수 있는 병명이 담긴 airportData와 현재 환자의 병명 목록 patientData가 주어집니다. 입력 data의 첫 번째 값이 airportData, 두 번째 값이 patientData입니다. 방문할 공항의 이름을 리스트로 반환하는 코드를 작성하세요.


제한 사항

  • airportData의 각 공항은 name(공항 이름), distance(공항까지의 거리, 단위: km), treatableDiseases(치료 가능한 병명 리스트) 키를 가진 딕셔너리입니다.
  • patientData는 발생한 환자의 병명 리스트를 포함합니다.
  • 모든 환자의 병을 치료할 수 있는 공항 묶음은 항상 있습니다.
  • 환자의 병을 모두 치료할 수 있는 공항 묶음 중 distance의 합이 가장 작은 묶음을 고르고, 그 공항 이름을 distance가 작은 순서대로 리스트에 담아 반환합니다.
  • 공항 사이의 이동 거리는 따로 계산하지 않고, 고른 공항들의 distance를 더한 값을 그 묶음의 거리로 봅니다.
  • 공항은 1개 이상 10개 이하이고, 공항까지의 거리는 모두 다릅니다.
  • distance의 합이 가장 작은 묶음이 하나뿐인 입력만 주어집니다.

입출력 예

입력

[
    [
        # airportData
        {
            "name": "Airport A", 
            "distance": 500, 
            "treatableDiseases": ["Disease A", "Disease B"]
        },
        {
            "name": "Airport B", 
            "distance": 300, 
            "treatableDiseases": ["Disease C"]
        },
        {
            "name": "Airport C", 
            "distance": 400, 
            "treatableDiseases": ["Disease B", "Disease C"]
        }
    ], 
    ["Disease A", "Disease C"] # patientData
]

출력

["Airport B", "Airport A"]

입출력 설명:

  • "Disease A"는 Airport A만, "Disease C"는 Airport B와 Airport C가 치료할 수 있습니다. Airport A와 Airport B를 고르면 거리 합이 800, Airport A와 Airport C를 고르면 900이므로 Airport A와 Airport B를 고르고, 거리가 가까운 순서대로 ["Airport B", "Airport A"]를 반환합니다.

예시 테스트

#입력기대값
1[[{"name": "Airport A", "distance": 500, "treatableDiseases": ["Disease A", "Disease B"]}, {"name": "Airport B", "distance": 300, "treatableDiseases": ["Disease C"]}, {"name": "Airport C", "distance": 400, "treatableDiseases": ["Disease B", "Disease C"]}], ["Disease A", "Disease C"]]["Airport B", "Airport A"]
2[[{"name": "Airport D", "distance": 200, "treatableDiseases": ["Disease D", "Disease E"]}, {"name": "Airport E", "distance": 600, "treatableDiseases": ["Disease F"]}, {"name": "Airport F", "distance": 400, "treatableDiseases": ["Disease D", "Disease F"]}], ["Disease D", "Disease F"]]["Airport F"]
3[[{"name": "Airport G", "distance": 250, "treatableDiseases": ["Disease G", "Disease H"]}, {"name": "Airport H", "distance": 350, "treatableDiseases": ["Disease I"]}, {"name": "Airport I", "distance": 450, "treatableDiseases": ["Disease G", "Disease I"]}], ["Disease G", "Disease I"]]["Airport I"]

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.