[바미] 랜선 자르기

문제

https://www.acmicpc.net/problem/1654

 

코드

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

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

function getMaxLanCableLength(K, N, lengths) {
    let low = 1;
    let high = Math.max(...lengths);
    let result = 0;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const totalCables = lengths.reduce((acc, len) => acc + Math.floor(len / mid), 0);

        if (totalCables >= N) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return result;
}

const maxLength = getMaxLanCableLength(K, N, lengths);
console.log(maxLength);

 

문제 해설

이 문제는 이진 탐색(Binary Search)를 활용하여 최적의 랜선 길이를 찾는 전형적인 문제인데 효율적으로 이진 탐색을 하기 위해 랜선의 길이를 조정하면서 가능한 최대 길이를 찾아 문제를 풀었습니다.

 

시간 복잡도

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

 

이진 탐색의 시간 복잡도는 𝑂(log⁡𝐿)이며, 각 단계에서 모든 랜선 길이를 합산하는 데 𝑂(𝐾)가 소요됩니다.

따라서 전체 시간 복잡도는 𝑂(𝐾log⁡𝐿)이 됩니다. 여기서 𝐿은 가장 긴 랜선의 길이를 의미합니다.

공간 복잡도

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

 

공간 복잡도는 입력 데이터와 해시셋을 저장하는 데 필요한 𝑂(𝐾)입니다. 이진 탐색 과정에서 추가적인 메모리가 거의 필요하지 않기 때문에 전체 공간 복잡도는 𝑂(𝐾)이 됩니다.