[Python] 백준 2212번 - 센서

문제: https://www.acmicpc.net/problem/2212

2212번: 센서

 

그리디 알고리즘을 적용해 문제를 풀었다.

처음에는 집중국을 기준으로 원으로 자료를 수집한다고 생각했는데, 예제를 보면 집중국 기준으로 단방향으로만 수집을 한다는 힌트를 얻을 수 있다.

 

주어진 센서들을 총 K개(집중국의 개수)만큼 그룹을 지어주면 되는 문제이다.

따라서 센서들 간의 거리를 저장하는 별도의 리스트를 만들어주고, 리스트를 내림차순으로 정렬한다.

K개의 그룹을 만들어주려면 센서들 간의 거리를 저장하는 리스트에서 K-1개의 원소를 제거해주면 된다.

(삭제된 원소를 기점므로 그룹이 나뉘어지기 때문이다.)

 

로직은 맞는 것 같은데, 2번의 Index Error가 떴다.

1. N < K 인 경우, 즉 센서보다 집중국의 개수가 많이 들어오는 경우이다. 이 경우 집중국을 센서마다 설치해주면 되므로 집중국의 수신가능 영역은 항상 0이된다.

2. 센서의 좌표가 동일한 경우, 센서간의 거리를 저장하는 리스트에 값을 저장하지 않도록 설정했다. 하지만 이렇게 풀면 popleft()연산을 할때 Index Error가 발생할 수 있다. 따라서 센서 좌표가 동일해도 0이라는 값을 리스트에 추가해주어야한다.

 

코드는 다음과 같다.

from collections import deque

n = int(input())
k = int(input())
sensor = list(map(int, input().split()))
sensor.sort()
dist = []

for i in range(n-1):
    dist.append(sensor[i+1]-sensor[i])
dist.sort(reverse=True)
dist = deque(dist)

if n > k:
    for _ in range(k-1):
        dist.popleft()
    print(sum(dist))
else:
    print(0)