[JAVA] 백준 알고리즘 1654번 (랜선 자르기)

문제

---

이번에 다뤄볼 문제는 1654번 문제 '랜선 자르기'입니다.

이 문제는 이분탐색을 활용하여 해결 할 수 있습니다.

 

이분탐색(Binary Search)이란 이미 정렬되어 있는 배열에서 탐색 범위를 반씩 줄여 가며 찾고자 하는 값을 찾는 탐색 방법인데요.

검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘입니다.

검색 범위에 해당하는 하한값, 상한값을 기준으로 중간값부터 탐색을 시작하는 방식이고 이에 대하여 1부터 100까지의 범위에서 77이란 숫자를 찾는 과정을 통해 예를 들어보겠습니다.

 

[파이썬 알고리즘 인터뷰] p.516, 책만, 2020

 

첫 시작은 하한값(1)과 상한값(100)의 중간값인 50부터 시작을 합니다. 찾고자 하는 77의 경우 중간값보다 큰 값이기 때문에 하한값(1)을 중간값(50)으로 상향 조정하여 재정의 합니다. 이렇게 될 경우 이제 하한값(50), 상한값(100)의 범위에서 탐색을 시작하게 되고 이때의 중간값은 75가 됩니다. 위의 과정을 반복하여 하한값(75), 상한값(100)의 범위가 재정의 되었을때 중간값은 87입니다. 이번엔 이전과 다르게 중간값(87)이 77보다 크기 때문에 반대로 상한값(100)을 중간값(87)으로 하향 조정하여 재정의 합니다. 이러한 과정을 탐색의 목적인 77을 찾을때까지 진행하게 됩니다.

 

이렇게 이진탐색에 대하여 알아보았다면 이제 문제로 넘어가보도록 하겠습니다.

문제에서는 "동일한 길이를 갖는 N개의 랜선"을 구할 수 있는 랜선 길이의 최대값을 알고싶어합니다.

처음 K개의 서로 다른 길이의 랜선이 주어지고 우리는 여기서 이진탐색을 위한 랜선길이의 최대값을 정의할 수 있습니다. 문제에서 예시로 주어진 경우를 보면 랜선길이 탐색을 위한 하한값은 1, 상한값은 802로 탐색의 범위를 지정하면 됩니다.

 

따라서 아래 코드를 보면 minLanLength(랜선 길이의 하한값)을 1로, maxLanLength(랜선 길이의 상한값)는 입력받은 K개의 서로 다른 랜선 중 가장 긴 랜선의 길이로 값을 갖게 됩니다.

그 다음 이 minLanLength와 maxLanLength의 중간값(lanLength)으로 각 K개의 랜선을 잘랐을때 얻을 수 있는 랜선의 개수를 토대로 이진탐색을 진행하면 됩니다.  만약 원하는 랜선의 개수만큼 얻지 못했다면 상한값을 하향조정하고 반대로 원하는 랜선의 개수를 구했거나 더 많이 구했다면 하한값을 상향조정 해줍니다.

 

이러한 과정을 반복하며 탐색을 진행하면 궁극적으로 문제에서 알고싶어했던 "동일한 길이를 갖는 N개의 랜선 길이의 최대값"을 구하게 됩니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long minLanLength = 1;
        long maxLanLength = 0;

        Scanner in = new Scanner(System.in);

        int k = in.nextInt();
        int n = in.nextInt();

        int[] kLanArray = new int[k];

        for (int i = 0; i < k; i++) {
            kLanArray[i] = in.nextInt();
            maxLanLength = Math.max(maxLanLength, kLanArray[i]);
        }

        while (minLanLength <= maxLanLength) {
            // 이분탐색을 위해 상한, 하한의 중간값으로 lanLength를 정한다.
            long lanLength = (minLanLength + maxLanLength) / 2;
            long lanCount = 0;
            for (int i = 0; i < k; i++) {
                lanCount += kLanArray[i] / lanLength;
            }
            if (lanCount >= n) {
                // 원하는 N개 만큼 나오가나 더 많은 랜선이 나온 경우 하한을 올려준다.
                minLanLength = lanLength + 1;
            } else {
                // 원하는 랜선의 개수를 만들지 못했다면 상한을 내려준다.
                maxLanLength = lanLength - 1;
            }
        }

        System.out.println(maxLanLength);
    }
}