[알고리즘] Swift -프로그래머스 연습문제 #181188(요격 시스템)

문제링크

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

프로그래머스

 

 

 

 

 

분석

A나라가 B나라를 침공했습니다.

B나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에
A나라는 B나라의 아이기스 군사 기지에 융단 폭격을 가했습니다.

A나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다.

이곳에는 백발백중을자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.

A나라와 B나라가 싸우고 있는 이 세계는 2차원 공간으로 이루어져 있습니다.

A나라가 발사한 폭격 미사일은 x축에 평행한 직선 형태의 모양이며 개국간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다.

B나라는 특정 x좌표에서 y축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한번에 요격할 수 있습니다.

단 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다.

요격 미사일은 실수인 x좌표에서도 발사할 수 있습니다.

각 폭격 미사일의 x좌표 범위목록이 주어질 때 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 리턴하는 함수를 완성하라.

 

풀이 과정

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

일단 타켓을 end를 기준으로 오름차순으로 정렬하면

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

여기에서 end와 다음 start를 비교하면 사이에 있는 지 끊겨서 뒤에 있는지 확인할 수 있음

 

 

풀이

import Foundation

func solution(_ targets:[[Int]]) -> Int {
    
    let sorted = targets.sorted { $0[1] < $1[1] }
    var end = Int.min
    var result = 0
    
    for sort in sorted {
        if sort[0] >= end {
            end = sort[1]
            result += 1
        }
    }
    
    return result
}

 

결과