[바미] 공유기 설치

문제

https://www.acmicpc.net/status?user_id=ckdqja135&problem_id=2110&from_mine=1

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, C] = input[0].split(' ').map(Number);
const houses = input.slice(1).map(Number);

houses.sort((a, b) => a - b);

function canPlaceRouters(distance) {
    let count = 1;
    let lastPlaced = houses[0];
    
    for (let i = 1; i < N; i++) {
        if (houses[i] - lastPlaced >= distance) {
            count++;
            lastPlaced = houses[i];
        }
        if (count >= C) {
            return true;
        }
    }
    return false;
}

function getMaxRouterDistance() {
    let low = 1;
    let high = houses[N - 1] - houses[0];
    let result = 0;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (canPlaceRouters(mid)) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return result;
}

const maxDistance = getMaxRouterDistance();
console.log(maxDistance);

문제 해설

이 문제는 이진 탐색(Binary Search)을 활용하여 최적의 공유기 설치 간격을 찾는 문제입니다. 

주어진 집의 위치에서 공유기 사이의 최소 거리를 최대로 하려면, 가능한 최대 간격을 찾는 과정을 이진 탐색을 통해 해결할 수 있습니다.

 

공유기 사이의 거리를 이진 탐색을 통해 결정하게 됩니다.

 

먼저 가능한 최소 거리(low)는 1, 최대 거리(high)는 집들 간의 최대 거리(집 위치 배열에서 최댓값 - 최솟값)로 설정해줍니다.

중간 거리(mid)를 계산하여 그 거리로 공유기를 설치했을 때, 모든 공유기를 설치할 수 있는지 확인합니다.

모든 공유기를 설치할 수 있다면 더 큰 거리로 시도해보고, 그렇지 않다면 더 작은 거리로 다시 시도합니다.

 

이러한 과정을 반복하여 최적의 거리를 찾는 방식입니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

이진 탐색의 시간 복잡도는 𝑂(log⁡ 𝐷)이며, 각 단계에서 모든 집을 순회하여 공유기를 설치할 수 있는지 확인하는 데

𝑂(𝑁)가 소요됩니다.

 

따라서 전체 시간 복잡도는 𝑂(𝑁 log ⁡𝐷)입니다. 여기서 𝐷는 집 위치 배열에서 최댓값 - 최솟값입니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

공간 복잡도는 입력 데이터를 저장하는 데 필요한 𝑂(𝑁)입니다. 

이진 탐색 과정에서 추가적인 메모리가 거의 필요하지 않기 때문에 전체 공간 복잡도는 𝑂(𝑁)입니다.