[코드트리] 개발자들의 거리두기

📁 문제

N명의 개발자들은 일직선상에 서있습니다. 그들 중 일부는 전염병에 감염되었고, 감염된 개발자는 양수 거리 R 이내에 있는 개발자들을 곧바로 감염시킵니다. 거리 R은 알 수 없는 상황에서, 처음에 감염된 개발자 수의 최솟값을 구하는 프로그램을 작성해보세요.

https://www.codetree.ai/problems/developers-keeping-distance/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

 

📁 풀이

import sys

n = int(input())
r = sys.maxsize
developers = [0] * 1000000
max_dev = 0
infec_devs = []
for i in range(n) :
    location, infection = map(int, input().split())
    if infection == 0 :
        developers[location] = 2
    else :
        developers[location] = 1
        infec_devs.append(location)

    if max_dev < location :
        max_dev = location
infec_devs.sort()
distance = []
for i in range(len(infec_devs)-1) :
    distance.append(infec_devs[i+1]-infec_devs[i])

for i in range(1, max_dev+1) :
    if developers[i] == 2 :
        for j in range(1, i+1) :
            cur_r = sys.maxsize
            if developers[i-j] == 1 or developers[i+j] == 1 :
                cur_r = j
                break
        if r > cur_r :
            r = cur_r

bins = 0
for i in distance :
    if i <= r-1 :
        bins += 1

print(len(infec_devs)- bins)