문제 이해

숫자 배열이 존재한다. 그리고 특정 수 M이 주어질 것이다.
내가 K 숫자를 지정했다고 가정하자.

만약 배열에 저장된 숫자가 K 이하라면 아무 상황도 일어나지 않는다.
반대로 배열에 저장된 숫자(T)가 K 초과라면, T-K만큼의 data가 생성된다.
이렇게 생긴 T-K data를 모두 합쳐 M 이상을 만들어야 한다.

이 때 내가 지정할 수 있는 K 중 최댓값을 구하는 문제이다.

문제 풀이

배열에서 내가 얻을 수 있는 데이터는 T-K, 혹은 0이다. 즉, T-K가 음수라면 0을 얻을 수 있는 것이고, 양수라면 T-K를 얻을 수 있는 것이다.
따라서 Math.max(0, T-K)를 통해 모든 배열에 대해 내가 얻을 수 있는 data를 구할 수 있을 것이다.

Brute-Force Algorithm으로 생각해보자. K = 1로 지정한 이후, 배열의 최댓값까지 T-K data의 합을 구하는 과정을 모두 수행해본 다음, 처음으로 data의 합이 M이상이 되는 K를 출력하면 된다.

문제는 범위이다. 이 문제에서 나무의 최대값의 범위는 주어지지 않았다. 즉, 가장 큰 값이 매우 클 경우 Time Complexity가 매우 커질 위험성이 존재한다.

문제를 잘 생각해보자.

$ans\ =\ \sum _{\ }^{\ }\max _{ }^{ }\left(arr\left[i\right]-K,0\right)$

1. ans < M : 정답이 될 수 없는 K이다. ans을 크게 해야 한다. 따라서 K값을 작게 해야 한다.

2. ans >= M : 정답이 될 수 있는 K이다. 하지만 K중 최댓값을 찾아야하기 때문에 계산을 멈추지는 않는다.
   이 때 K를 저장한 이후 K를 크게 하여 다시 ans를 구해본다.

Case를 2가지로 나누고, 한 개 Case를 만족할 때 일정 구역은 확인하지 않아도 된다..? 이분 탐색을 위한 완벽한 조건이다. 따라서 이분 탐색을 통해 문제를 해결하면 될것이다.

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int N;
	static long M;
	static long[] arr;
	
	static void tree(long right) {
		long mid;
		long left = 0;
		long ans = 0;
		
		while(left <= right) {
			long sum = 0;
			mid = (left + right)/2;
			
			for(int i = 0;i<N;i++) {
				sum+=Math.max(0,arr[i] - mid);
                // ans[i] - mid가 음수일 경우, 내가 얻을 수 있는 나무는 0
                // 즉, data를 0으로 처리하여 sum에 더해줌
			}
			
			if(sum>=M) {
                // ans >= M인 경우. 위의 문제 풀이 2번 Case이다.
                // 이 때의 mid는 답이 될 가능성이 있기 때문에 
                // ans에 저장해 놓아야 한다.
				left = mid+1;
				ans = mid;
			}
			else {
                // ans < M인 경우. 문제 풀이 1번 Case이다.
				right = mid - 1;
			}
		}
		
		System.out.println(ans);
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();

		N = sc.nextInt();
		M = sc.nextLong();
		arr = new long[N];
		
		long max = Integer.MIN_VALUE;
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextLong();
			max = Math.max(max, arr[i]);
		}

		tree(max);
        // max에는 숫자 배열의 최댓값이 저장되어 있다.
        // 절대 내가 임의로 지정할 K는 max보다 클 수 없다.
        // 따라서, left = 0, right = max로 지정해서 이분 탐색을 진행한다.
	}
	
	static class FastReader // 입력을 빨리 받기 위한 Class. 생략.
}

결과

• 4번째 줄 틀렸습니다 : 출력 초과. 실수로 디버깅 때 확인을 위한 출력 문구를 지우지 않아 생긴 문제이다.

• 3번째 줄 틀렸습니다 : M은 Long형 data이기 때문에 이분 탐색의 while문에서 data 값의 합을 저장하는 sum 또한 Long 자료형이여야 한다. 하지만 int로 지정하여 발생한 문제이다.

• 첫번째 맞았습니다와 2번째 맞았습니다 시간 차이가 매우 큰 이유

  • 2번째 맞았습니다 때는 나무 길이를 입력받은 숫자 배열을 Sorting 시켰다. 이는 이분 탐색 때 무조건 Sorting시켜야 한다는 생각에 수행하였다.

  • 하지만 코드를 제출한 이후 생각해보니 굳이 Sorting한 Array를 활용하지 않는다는 것을 알게 되었다. 결국 모든 Array를 Search해야하기 때문이다.

  • 따라서 Sorting을 포기하였더니 시간이 매우 줄어들었다. 이번 코드 같은 경우, left와 right가 배열에서 주어지는 것이 아닌 자연수인 상황이다(1이상 max이하에서 찾기). 자연수는 무조건 Sorting되어 있는 값이다. 어느 부분을 사용하여 이분 탐색의 left, right를 활용할지, 또한 Sorting 한 것을 활용하는 부분이 존재하는지 생각해 봐야 할 것 같다.