[자바/이진탐색] BOJ 16401. 과자 나눠주기

문제 

16401번: 과자 나눠주기

해석

개인적으로는 헤맨 문제인데... 로직은 이진탐색의 기본 유형이다.

 

내가 나눠주고자 하는 과자 길이 X가 무엇인가를 찾는 문제로, 단순하게 for loop만을 이용하여 모든 길이에 대하여 탐색하는 로직은 O(n)인데 10억까지 탐색해야 하므로 불가능한 로직이다. 따라서 내가 찾는 X를 찾는 로직을 O(logN)으로 찾을 수 있는 이진탐색이 가능한지 봤는데, 가능했다.

 

헤맨 부분은 X를 찾는 방식이 어떻게 되느냐 하는 부분이었다. 주어진 길이 배열 속 숫자를 어떻게 처리해야 내가 원하는 x를 찾을 수 있을까라는 생각에 갖혀서 한참을 고민하다가, 결국 근본적으로 내가 찾는 X라는 길이는 주어진 숫자에 얽매이는 개념이 아니라 주어진 범위 내에서 해당 배열에 대보면서 맞고 틀리고만 비교하면 되는 문제였다.

 

따라서 주어진 배열은 정렬 되든 말든 관심 없는 거고, 나는 1부터 10억까지의 숫자 중 어떤 숫자 X가 과자의 길이로 선택되어야 주어진 과자들로 공평하게 줄 수 있는지 체크하면 된다.

코드

알고리즘 : 이진탐색

시간복잡도 : O(logN)

package 알고리즘연습.boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Stream;

public class BOJ_16401_과자나눠주기 {
    // 시간 : 588ms
    // 메모리 : 115128 KB

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

        // init
        int[] cookies = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // binary search
        int left = 1;
        int right = (int) 1e9;

        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = Arrays.stream(cookies).map(cookie -> cookie / mid).sum();
            if (cnt >= nephewsCnt) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        int ans = right;
        // 항상 left가 아니라 right 가 ans인 이유 : 동일한 경우에도 최대 값을 찾기 위해 left = mid + 1;을 통해 가능한 x중 가장 큰 x를 연산하고자 했고, 가장 마지막 연산에서 left가 정답에서 + 1 되므로
        // 그렇게 처리되지 않는 right가 정답임. 혹시 만약 cnt == nephewCnt인 경우에 right = mid - 1;을 해버리면 최대인 x를 찾을 수 없으므로 정답을 얻을 수 없음.
        System.out.println(ans);
    }
}

레슨런

로직만 봤을 때에는 이진탐색의 기본 유형이지만, 개인적으로 알고리즘 센스가 없는 나에겐 꽤나 어려웠고 인상적인 문제였다. 평소처럼 "입력 데이터를 어떻게 만져야 풀 수 있을까"라는 생각에 사로잡혀서 방법을 찾으려 한참 헤매다가 나중에 아차 했었다... 문제를 차근차근 분석하는 과정에서 내가 정말 구하고 싶은 X가 무엇이고, 이걸 찾는 방법에 대하여 입력값을 처리하는 것에 갖히지 말고 열린 마음으로 집중해야한다는 나름의 레슨런이 있었던 문제라 알고리즘 기록장을 오랜만에 켰다.