BOJ-2212 센서 Swift

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

내가 푼 풀이

- 예제입력 1로 주어진 센서를 아래와 같이 표현하면 다음과 같다.

- 센서위치를 배열로 표현후 오름차순으로 정렬한다. [ 1, 3, 6, 6, 7, 9]

- 해당 입력으로 주어졌을때, 집중국의 수신가능 영역의 길이의 합 최솟값은 2 + 3 = 5이다.

- 정답을 도출하기 위해서, 각 센서사이의 거리를 구한다.

 

- 각 센서사이의 거리를 구한 후 오름차순으로 정렬하면 [0, 1, 2, 2, 3] 이 된다.

- 여기서 우리는 k개의 집중국을 설치하게 되는데,

- 집중국의 수신가능 영역의 길이의 합이 최소로 되게끔 k개의 집중국을 설치하면, 집중국과 집중국 사이의 빈 공간이 k-1개가 생긴다.

- 빈 공간 k-1개를 최대로 만들면 길이의 합이 최소로 된다.

- 센서사이의 거리 배열이 오름차순으로 정렬되어 있으니, k-1개만큼 마지막위치를 빼주고, 배열의 합을 구해주면 된다.

 

- 센서 위에 집중국을 설치하면, 그 집중국의 수신가능 영역이 0 이어도 같은 위치의 센서와 수신가능하다.

- 만약 센서의 개수와 집중국의 개수가 같다면, 센서 위에 집중국을 설치하면 모두 수신가능하므로 최솟값은 0이 된다.

 

위 방법으로 코드로 구현해 보자

 

import Foundation

var count = Int(readLine()!)!
var n = Int(readLine()!)!

// 배열을 입력받고, 오름차순으로 정렬
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
arr.sort{ $0 < $1}

// 센서의 갯수가 1이거나 집중국의갯수와 같다면 최소합은 0이된다
// 센서사이의 거리를 구해 오름차순으로 정렬한 후 k-1개만큼 길이가 긴 범위를 빼준다.
if count == 1 || count == n {
    print(0)
} else {
    var sub = [Int]()
    for i in 0..<arr.count-1 {
        sub.append(arr[i+1] - arr[i])
    }
    sub.sort{ $0 < $1}
    for i in 0..<n-1 {
        sub.removeLast()
    }
    print(sub.reduce(0, +))
}