[백준] 1654번 : 랜선 자르기 - JAVA

1654 랜선자르기

 

 

이 문제를 처음 봤을 때 어떤 방식으로 풀어야 하는지 25분 정도 고민을 한 것 같다.

 

왜냐하면 아래와 같은 방식이나 이와 유사한 방식만 생각이 들었기 때문이다.

1. 입력받은 K[i]들을 다 더한 후 N으로 나눈다.
2. 나눈 몫을 1씩 줄여가며 각 랜선의 길이에 나눈다(2중 반복문).
3. 나눈 몫을 누적하여 N과 동일할 때까지 반복한다.

이러한 풀이는 시간복잡도가 $O(n*m)$ (사실상 $O(n^2)$)이라서 풀 수 없다.

해당 문제는 시간제한이 2초이고 주어진 값의 범위가 $1 <= K <= 10000$, $1 <= K[i] < 2^{31}$이기 때문에 다른 방식을 생각해야 했다.

 

 

 

결론적으로 이 문제는 이분탐색 알고리즘을$O(\log_2 n)$ 사용하면 해결된다.

그러나 주의할 점이 있다.

 

문제 해결 시 주의사항

1. 오버 플로우를 조심해라.

- 이분탐색 로직 중 left와 right 변수를 더할 때 $2^{31}-1$을 초과할 수 있으니 long으로 변수를 선언해야 한다.

 

2.  0으로 나누어지는 경우를 조심해라.

- 아래 소스에서 left와 right를 더한 값이 0 또는 1이라면 mid 값은 0이 되어 Exception이 발생한다.

java.lang.ArithmeticException: / by zero 

 

아래 구현소스는 주의사항을 적용하여 제출한 소스이다.

 

성공소스1 (오름차순 정렬 후 배열의 마지막 요솟값(최댓값)을 right로 세팅)

시간복잡도: $O(m \log_2 n)$

/**
 * 랜선 자르기 - 이분 탐색
 */
public class _1654 {

    private static long binarySearch(int[] arr, int n) {
        long left = 0L;

        // 배열에서 가장 큰 수
        long right = arr[arr.length - 1];
        long result = 1;

        // left + right > 1 조건: mid가 0이 되면 안된다.
        while (left <= right && left + right > 1) {
            // int의 경우 left와 right 더해서 2^31-1을 초과한 경우 오버플로우가 발생한다.
            long mid = (left + right) >>> 1;
            int cntLine = 0;

            for (int i : arr) {
                cntLine += (int) (i / mid);
            }

            if (cntLine < n) {
                right = mid - 1;
            } else {
                left = mid + 1;
                result = mid;
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[k];

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

        Arrays.sort(arr);

        System.out.println(binarySearch(arr, n));
        br.close();
    }

}

 

 

성공소스2 (Integer 최댓값$2^{31}-1$을 오른쪽 값으로 세팅)

시간복잡도: $O(m \log_2 n)$

/**
 * 랜선 자르기 - 이분 탐색
 */
public class _1654 {

    private static long binarySearch(int[] arr, int n) {
        long left = 0L;
        long right = Integer.MAX_VALUE;

        // left + right > 1 조건: mid가 0이 되면 안된다.
        while (left <= right && left + right > 1) {
            // int의 경우 left와 right 더해서 2^31-1을 초과한 경우 오버플로우가 발생한다.
            long mid = (left + right) >>> 1;
            int cntLine = 0;

            for (int i : arr) {
                cntLine += (int) (i / mid);
            }

            if (cntLine < n) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left - 1;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[k];

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

        System.out.println(binarySearch(arr, n));
        br.close();
    }

}

 

 

당연히  K[i]의 개수가 많을 수록 구현소스2가 실행시간이 빠르다(큰 차이는 없겠지만...).

 

 

생각보다는 쉬운 문제였지만 오버플로우나 0으로 나누는 것을 미리 인지하지 못해 시간이 지연되었다.

다음에는 위 2가지 주의할 점에 똑같은 실수를 반복하지 않게 자주 복기를 해야겠다.

(그러려고 블로그 시작하긴 했지~)