공유기 설치 ( 2110 번 )

2110번: 공유기 설치

 

---

🧠 알고리즘

• 이진 탐색 (Binary Search)

 

✔️ 동작 방식

• 공유기 설치 문제로, 집 좌표 간의 최소 거리(mid) 를 기준으로 공유기를 설치할 수 있는지 탐색한다.
• 집 좌표를 오름차순 정렬한다.
• 최소 거리의 범위를 l = 1, r = (가장 먼 집 - 가장 가까운 집) 으로 설정한다.
• 중간 거리 mid = (l + r) // 2를 기준으로,
  • 첫 번째 집부터 시작해 이전 설치 지점(now_point) 에서 mid 이상 떨어진 집에 공유기를 설치하며 개수를 센다.
• 설치된 공유기 수(count)가 설치해야 할 수(c) 이상이면,
  • mid 거리로 설치가 가능하므로 거리 값을 더 늘려보기 위해 l = mid + 1 로 이동한다.
  • 이때 가능한 거리 후보 answer = mid 를 기록한다.
• 반대로 공유기 수가 부족하면 거리 간격이 너무 넓다는 뜻이므로 r = mid - 1 로 좁힌다.
• 탐색이 끝나면 가장 인접한 공유기 사이의 최대 거리(answer) 를 반환한다.

---

 

🧾 코드

import sys

def _main():
    l, r = 1, n_list[-1] - n_list[0]

    while l <= r:
        now_len = (l + r) // 2
        wife, now_point = 1, n_list[0]

        for n_value in n_list:
            if now_point + now_len <= n_value:
                wife += 1
                now_point = n_value

        if wife >= c:
            answer = now_len
            l = now_len + 1
        else:
            r = now_len - 1

    return answer
        

n, c = map(int, sys.stdin.readline().rstrip().split())
n_list = sorted(list(int(sys.stdin.readline().rstrip()) for _ in range(n)))

print(_main())

---

 

⏱️ 시간 복잡도

house.sort() : 파이썬 정렬 알고리즘 ( 선형 로그 시간 복잡도 )

while l <= r : 이진 탐색 ( 로그 시간 복잡도 )
	for idx in range(1, n) : 집을 순회하며 설치 유무 확인 ( 선형 시간 복잡도 )
    
해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )