[99클럽 코테 스터디 11일차 TIL] 과자 나눠주기 (binary search)

📌 키워드 

• 이분 탐색 

📌 문제 분석 

 

시간복잡도 생각 안하면 어떻게 풀 수있을까? 

 

최대 길이 만큼 Max(L) 반복을 하며, 주어진 과자(N)개에 대해  각 길이로 나누었을때 조카의 수만큼 동일한 길이로 줄  수 있는지 확인한다. 이 경우, 최악의 경우 Max(L) * N 으로 1초 이내에 풀이 할 수 없다. 

 

그렇다면 탐색의 횟수를 줄여야 하는데, 어떻게 줄일 수 있을까? 

나의 경우에는 이분 탐색 방법을 썼다. Max(L) 만큼 탐색하는 것이 아니라 탐색의 범위를 반씩 줄여나가면서 log(Max(L)) = 9  (사실은 밑이 2라서 조금 더 크긴 하다.) 의 시간으로 줄인다. 개인적이로 이분탐색은 정말 획기적인 알고리즘중 하나라고 생각한다. 

 

따라서 예상되는 최종 시간 복잡도는  O(Nlog(Max(L))

 

left = 1. right = Max(L) 를 초기 값으로 설정하고 

left  <= right 를 만족하는 동안만 while문사용하여  아래의 로직을 반복한다. 

--------------------------------------------------------------------------

1. mid 값을 설정한다. mid = (left + right) / 2 

2  mid 값의 길이를 사용하였을때 M만큼 나눌 수 있는지 판별 

if )  mid 값의 길이를 사용하였을때 조카의 수 M 만큼 나누어줄 수 없다?  => 현재 mid 값보다 큰 길이도 M 만큼 나누어 줄 수 없다는 뜻. 

            right = mid - 1

else ) mid 값의 길이를 사용했을때 M만큼 나누어 줄 수 있다? => mid 보다 큰 길이일때도 M만큼 나누어줄 수 있는 여지가 있음. 

             left = mid + 1  

             result = mid (조건을 만족하는 mid 값을 전역 변수 result에 저장해둠. 최대 길이를 구하는 것이므로 mid 보다 큰 것이 조건을 만족한다면 교체)

-----------------------------------------------------------------------------

3.  result 에 저장된 값 출력 

 

class Main {
    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = 0;  int n = 0;
        String[] inputs = br.readLine().split(" ");
        m = Integer.parseInt(inputs[0]);
        n = Integer.parseInt(inputs[1]);

        int[] sticks = new int[n];
        int max = -1;
        inputs = br.readLine().split(" ");
        for (int i=0; i<n; i++){
            sticks[i] = Integer.parseInt(inputs[i]);
            max = Math.max(max,sticks[i]);
        }

        // binary_search log(10 ** 9 ) * N  최대 : 6 * N
        int left = 1; int right = max;
        int result = 0;
        while(left <= right){
            int mid = (left + right) / 2;
            int cnt = 0;

            for (int i=0; i<n; i++){
                cnt += sticks[i] / mid;
            }

            if (cnt >= m){
                left = mid + 1 ;
                result = mid ;
            }else{
                right = mid -1;
            }
        }
        System.out.println(result);
    }
}

 

📌  주의 

left == right 인 순간에 대해서도 탐색을 해야한다.

예를 들면  left 5 , mid =6, right 7 로 사이 간격이 1이라고 할때,  

left = mid + 1 로 이동한다고 생각해보자

 

left = 7, right = 7로 같아지므로 while문이 종료되고 mid 값인 7은 탐색이 안된다. 

이  이유로 초반에 케이스 2에 대해 결과를 6을 출력하는 문제가 있었다.