[JAVA] 알고리즘 문제풀이 입문 6-9, 6-10

강의: https://inf.run/w779

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

 

6-9번

import java.util.Arrays;
import java.util.Scanner;

public class Main{
  public int count(int[] arr, int capacity){
    int sum = 0, cnt = 1;
    for(int x : arr){
      if(sum + x <= capacity) sum += x;
      else{
        cnt++;
        sum = x;
      }
    }
    return cnt;
  }

  public int solution(int n, int m, int[] arr){
     int answer = 0;

    // int lt = 0, rt = 0;
    // for(int x : arr){
    //   if(lt < x) lt = x;
    //   rt += x;
    // }
    int lt = Arrays.stream(arr).max().getAsInt();
    int rt = Arrays.stream(arr).sum();

    while(lt <= rt){
      int mid = (lt+rt)/2;
      if(count(arr, mid) <= m){
        answer = mid;
        rt = mid-1;
      }else{
        lt = mid+1;
      }
    }
    return answer;
  }

  public static void main(String args[]){
    Main T = new Main();
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int m = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
      arr[i] = in.nextInt();
    }
    in.close();

    System.out.print(T.solution(n, m, arr));
  }
}

 

6-10번

import java.util.Arrays;
import java.util.Scanner;

public class Main{
  public int count(int[] arr, int mid){
    int cnt = 1;
    int pre = arr[0];
    for(int i = 1; i < arr.length; i++){
      if(arr[i]-pre >= mid){
      cnt++;
      pre = arr[i];}
    }
    return cnt;
  }

  public int solution(int n, int c, int[] arr){
     Arrays.sort(arr);
     int answer = 0;

     int lt = 1, rt = arr[n-1];

    while(lt <= rt){
      int mid = (lt+rt)/2;
      if(count(arr, mid) >= c){
        answer = mid;
        lt = mid+1;
      }else{
        rt = mid-1;
      }
    }
    return answer;
  }

  public static void main(String args[]){
    Main T = new Main();
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int c = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
      arr[i] = in.nextInt();
    }
    in.close();

    System.out.print(T.solution(n, c, arr));
  }
}