[Java+Python]2110번, 공유기 설치

목차

이진 탐색

 

[Java+Python]1920번, 수 찾기

[Java+Python]1654번, 랜선 자르기

[Java+Python]2805번, 나무 자르기

[Java+Python]2805번, K번째 수

[Java+Python]12015번, 가장 긴 증가하는 부분 수열 2

문제

 

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 $x_1, ..., x_N$이고, 집 여러 개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 

최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 

가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈칸을 사이에 두고 주어진다. 

둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 $x_i (0 ≤ x_i ≤ 1,000,000,000)$가 한 줄에 하나씩 주어진다.

 

출력

 

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

풀이

 

계속되는 이진 탐색 문제이다. 이번엔 집의 좌표가 주어지고 설치해야 하는 공유기의 개수가 주어진다.

 

집의 좌표마다 공유기를 설치하되, 공유기 사이의 거리가 최대가 되도록 하고, 그 최대 거리를 출력하는 문제이다.

 

이전까지의 이진 탐색에 익숙해져 있다면 크게 어려울 것이 없다.

 

알고리즘은 다음과 같다.

 

1. 집의 개수 n과 공유기의 개수 c를 입력받은 뒤, 각 집의 위치를 크기 n인 배열(리스트) houses에 저장한다.
2. 이진 탐색을 수행하기 위해 houses를 오름차순으로 정렬한다.
3. left = 1, right = houses[n - 1] - houses[0]으로, 답을 저장할 answer = 0으로 초기화한다.
4. 이진 탐색을 시작한다. left <= right인 동안 아래의 과정을 반복한다.
   
   
   1. mid = (left + right) / 2로, 시작점 start = houses[0]으로, count = 1로 초기화한다.
   2. houses 배열을 순회하면서 각 집과 start 사이의 거리를 계산하고 해당 거리가 mid보다 크거나 같으면
      count를 증가시키고 start를 현재 house의 위치로 갱신한다.
      (이 과정은 공유기가 두 대 이상이기 때문에 전체 길이의 절반을 넘는 값은 버리는 역할을 한다.)
   3. count >= c 라면 answer = mid, left = mid + 1로 갱신하고, 그 반대라면 right = mid - 1로 갱신한다.
5. 탐색이 종료된 후 answer를 출력한다.

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Prob2110 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		int[] houses = new int[n];

		for (int i = 0; i < n; i++) {
			houses[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(houses);

		int left = 1;
		int right = houses[n - 1] - houses[0];
		int answer = 0;

		while (left <= right) {

			int mid = (left + right) / 2;
			int start = houses[0];
			int count = 1;

			for (int house : houses) {
				int distance = house - start;
				if (distance >= mid) {
					count++;
					start = house;
				}
			}

			if (count >= c) {
				answer = mid;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}

		System.out.println(answer);
	}
}

 

Python

 

import sys

n, c = map(int, sys.stdin.readline().rstrip().split())
houses = [int(sys.stdin.readline().rstrip()) for _ in range(n)]

houses = sorted(houses)

left = 1
right = houses[n - 1] - houses[0]
answer = 0

while left <= right:
    mid = (left + right) // 2
    start = houses[0]
    count = 1

    for house in houses:
        distance = house - start
        if distance >= mid:
            count += 1
            start = house

    if count >= c:
        answer = mid
        left = mid + 1
    else:
        right = mid - 1

print(answer)

 

Performance