[백준/2. 분할정복,이분탐색] 1654번. 랜선자르기(JavaScript)

문제

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

 

알고리즘

이분탐색을 이용하는 문제이다.

 

최대 길이의 랜선을 구하는 것이 목표이다.

이분탐색을 하기 위해서는 먼저 정렬되어 있어야 하므로, 주어진 랜선 길이들을 정렬한다.

초기 left 값을 1로 right 값을 현재 주어진 랜선 길이 값들 중 가장 큰 input[K-1]로 설정한다.

중간 mid값은 ( left + right ) / 2로 둔다.

해당 mid값일 때 만들 수 있는 개수(리턴된 개수)가 원하는 것보다 적으면, 더 많이 리턴해야 하므로 쪼개는 기준치가 더 작아야 한다.

따라서 right를 mid-1로 설정하여, 다시 while문 조건을 확인하여 해당되면 반복문을 다시 돈다.

해당 mid값일 때 만들 수 있는 개수(리턴된 개수)가 원하는 것보다 많으면, 더 조금 리턴해야 하므로 쪼개는 기준치가 더 커야한다.

따라서 left를 mid+1로 설정하여, 다시 while문 조건을 확인하여 해당되면 반복문을 다시 돈다.

 

이 과정을 반복하다가 while문 조건을 벗어나면 

리턴된 카운트가 N이상이었을 때 크기를 비교하면서 설정된 answer를 출력한다.

 

이 문제 예시에서는 리턴된 카운트가 11이었을 때 200으로 answer가 설정되었고, 그 값을 출력했다.

 

이분탐색을 처음 알고리즘에 적용해보았는데,

최대 길이를 찾아가는데 이분탐색을 사용하는 것이 신기했고, 처음 감을 익힐 수 있는 문제였다.

 

약간 의문이 든 부분은 초기 right값을 설정할 때, 문제에서 주어진 최대 랜선의 길이가 2^31 - 1이어서,

right를 2^31 - 1로 설정하면 답이 굉장히 크게 나왔고,

주어진 입력 랜선길이들 중 가장 큰 것 input[K-1]으로 설정하면 예시 출력과 동일하게 문제가 잘 해결되었다. 🤔

 

이분탐색 문제를 여러번 풀어보면서 친해져야겠다..!

 

아래는 자바스크립트로 풀은 코드이다.

// 이분탐색 문제
// 배열이 이미 정렬되어 있어야 한다.

// 백준 입출력을 위한 코드
// const readline = require("readline");
// const rl = readline.createInterface({
//     input: process.stdin,
//     output: process.stdout,
// });

// let input = [];
// rl.on("line", function (line) { //여러줄 입력 
//     input.push(line)
//     //rl.close()가 없어서 계속입력 
//     //로컬에서 입력을 중지할려면 입력을 한 후 'ctrl + D'을 통해 입력 종료 
// }).on("close", function () {
//     // 이런식으로 적절하게 입력값을 처리해줘야한다. 
//     let KN = input.shift().split(' ').map(function (n) {
//         return parseInt(n, 10);
//     });
//     const K = parseInt(KN.shift(), 10);
//     const N = parseInt(KN.shift(), 10);
//     input = input.map(function (n) {
//         return parseInt(n, 10);
//     });
//     input = input.sort((a, b) => { return a - b });

//     solution(K, N, input);
//     //프로세스 종료 
//     process.exit();
// });

let input = [
    '4 11',
    '802',
    '743',
    '457',
    '539'
];

let KN = input.shift().split(' ').map(function (n) {
    return parseInt(n, 10);
});
const K = parseInt(KN.shift(), 10);
const N = parseInt(KN.shift(), 10);
input = input.map(function (n) {
    return parseInt(n, 10);
});
input = input.sort((a, b) => { return a - b });

function countReturn(len, K, input) {
    let count = 0;
    for (let i = 0; i < K; i++) {
        count += parseInt(input[i] / len, 10);
    }
    return count;
}

function solution(K, N, input) {
    let left = 1;
    let right = input[K - 1];

    let answer = 0;
    while (left <= right) {
        let mid = parseInt((left + right) / 2, 10);
        let retCount = countReturn(mid, K, input);
        // console.log(retCount, N);
        // console.log(left, mid, right);
        if (retCount >= N) {
            answer = Math.max(answer, mid);
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    console.log(answer);
}

solution(K, N, input);