99클럽 코테 스터디 4기 18일차 TIL - 백준: 센서(2212) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	2212	센서	그리디	골드5	Swift, Python

🚀 나의 접근 방법

예제 입력 1을 표현하면 아래와 같다. 빨간색이 센서, 초록색이 집중국, 파란색은 각 센서 간 거리이다.

각 센서 간 거리(파란색)는 총 4개이다. 위 상황에서는 가장 큰 파란색을 제외하고 나머지 파란색을 모두 더해주면 답을 얻을 수 있다.

집중국(K)이 2개이므로 센서 간 거리가 가장 큰 부분을 기준으로 나눠 집중국을 설치해야 집중국의 수신 가능 영역의 합을 최소로 만들 수 있다.

즉, 각 센서 간 거리들을 내림차순으로 정렬하고([3, 2, 2, 1]) 앞에서 K-1개만큼 제거 후 나머지를 모두 더하면 된다.

주의해야 할 점은 집중국의 개수 K가 센서의 개수 N보다 크거나 같을 때에는 모든 센서 위치에 집중국을 설치할 수 있으므로 답은 0이다. 이것을 분기 처리하지 않으면 범위 지정 시 오류가 날 수 있다.

✍️ 나의 코드

Swift

let N = Int(readLine()!)!
let K = Int(readLine()!)!
let coordis = Array(Set(readLine()!.split(separator: " ").map{ Int($0)! })).sorted()

if K >= N {
    print(0)
} else {
    var gaps: [Int] = []
    for i in 0..<coordis.count-1 {
        gaps.append(abs(coordis[i]-coordis[i+1]))
    }
    print(gaps.sorted(by: >)[(K-1)...].reduce(0, +))
}

Python

N = int(input())
K = int(input())
coordis = sorted(list(set(map(int, input().split(" ")))))

if K >= N :
    print(0)
else:
    gaps = []
    for i in range(len(coordis)-1):
        gaps.append(abs(coordis[i] - coordis[i+1]))
    print(sum(sorted(gaps, reverse=True)[K-1:]))

🤔 회고

그리디 문제가 익숙하지 않다. 더 많이 풀어보자.