[JAVA/백준/2343] 기타레슨 / 이분탐색

 

2343번: 기타 레슨

 

풀이 과정

처음에 갈피를 못잡아서 시간이 굉장히 오래 걸린 문제다
스터디원에게 문제 접근 방식을 듣고난 후 해결책을 찾았고 이분탐색에 대한 나의 고정관념을 깰 수 있었다

기존까지 풀었던 단순한 문제의 이분 탐색은 주어진 배열 내에서 최대 최소값을 찾는 문제였다
하지만 이번 문제는 배열을 그룹(블루레이)으로 나누고 그룹 내 요소 합의 최소값을 찾는 문제였기 때문에
요소 합의 최소를 이분 탐색으로 찾아야했다

 

따라서 배열 그룹의 합을 이진탐색으로 찾는 값(mid)으로 정하고 그 값(mid)을 넘지 않도록 각 그룹을 나눴다

mid 값을 넘지 않도록 그룹을 구성했을 경우 그룹의 개수가 입력으로 주어진 M보다 크다면, mid 값이 작은 것이기 때문에

left = mid + 1;

mid = (left + right) / 2

로 mid값을 증가시키고 반대의 경우라면 mid값을 감소시켰다

 

위를 이용해 답은 구했는데 변수가 너무 많아서 가독성이 좋지 않았다
문제 맞추는 데는 문제 없지만 다른 사람이 볼 때 이해하기 쉽도록 변수를 줄이고 공통된 부분은 최대한 묶으려고 했다
binarySearch 메서드와 main 메서드에서 공통으로 사용되는 변수는 파라미터로 넣어주지 않고 전역변수로 선언해서 공유되게 해서 해결 했다

 

결과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

  private static int N, M, max, sum;
  private static int[] videos;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st1 = new StringTokenizer(br.readLine());
    StringTokenizer st2 = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st1.nextToken());
    M = Integer.parseInt(st1.nextToken());
    videos = new int[N];
    max = 0;
    sum = 0;
    for (int i = 0; i < N; i++) {
      videos[i] = Integer.parseInt(st2.nextToken());
      max = Math.max(videos[i], max);
      sum += videos[i];
    }
    System.out.println(binarySearch(M));
  }

  private static int binarySearch(int M) {
    int left = max;
    int right = sum;

    while (left <= right) {
      int mid = (left + right) / 2;
      int temp = 0;
      int cnt = 1;
      for (int i = 0; i < N; i++) {
        temp += videos[i];

        if(temp > mid) {
          cnt++;
          temp = videos[i];
        }
      }
      if (cnt > M) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return left;
  }
}