이진 탐색의 문제 해결 포인트
- 특정 값에 대한 배열의 특정 인덱스 찾기
- 특정 조건을 만족하는 최대/최소값 찾기
중요한 점
어떤 것을 기준으로 범위를 좁힐 것인가? (변수 설정)
아이디어
이 문제에서는 숫자 카드 2 문제에서 배웠던 Upper Bound의 개념을 사용해야 합니다. 그 이유는 Lower Bound와 Upper Bound가 중복 원소가 있을 때 특정 값의 위치를 찾는 데 사용되기 때문입니다.
이진 탐색의 목적은, 특정 값에 대한 배열의 특정 인덱스를 찾기 위함입니다. 이를 확장하면, 특정 조건을 만족하는 최대/최소값을 쉽게 찾을 수 있습니다.
숫자 카드 2 문제
중복 원소의 개수를 구하기 위해 Array를 정렬한 후, key 값과 비교해가며 Upper Bound와 Lower Bound를 구해 두 값의 차이를 통해 중복 원소의 개수를 구했습니다.
- Upper Bound는 배열 내에서 key 값을 초과하는 값이 처음으로 나타나는 위치를 찾습니다. (Upper Bound - 1을 해줘야 key 값을 얻을 수 있음)
- Lower Bound는 배열 내에서 key 값이 처음으로 나타나는 위치를 찾습니다. (해당 값이 key 값을 바로 가리킴)
랜선 자르기 문제
중복된 갯수가 있을 때, 얻을 수 있는 최대 길이를 찾는 문제입니다.
어떤 것을 기준으로 범위를 좁힐 것인가?
- 이진 탐색 기본: 특정 key 값과 mid 값을 이용해 key와 arr[mid]의 값을 비교하여 lo와 hi를 좁혀나갑니다.
- 숫자 카드 2 문제: 특정 key 값과 arr[mid]를 비교하여 key < arr[mid]와 key <= arr[mid]로 나누어 상계와 하계를 구했습니다.
- 랜선 자르기 문제: 얻으려는 랜선의 개수가 key 값이 되고, 특정 mid 길이로 잘랐을 때 얻을 수 있는 랜선의 개수가 비교 대상이 됩니다.
결국 리턴받아야 하는 것은 길이에 대한 정보이기 때문에, 탐색해야 할 범위는 길이가 됩니다. 그러므로, mid, max, min은 길이에 대한 변수입니다.
- mid 값은 이진 탐색과 동일하게 mid = (min + max) / 2가 됩니다.
- count는 여러 개의 랜선에서 얻어낸 합이므로, for문을 이용해 누적해 나가야 합니다.
다음과 같이 작성할 수 있습니다:
// min의 초기값: 0, max: 입력받은 랜선 중 제일 큰 값
while (min < max) {
mid = (min + max) / 2;
long count = 0;
for (int i = 0; i < arr.length; i++) {
count += (arr[i] / mid);
} // 해당 mid으로 구할 수 있는 count 누적 합
if (count < N) {
max = mid; // count < N인 경우에 mid의 길이를 줄이기
} else {
min = mid + 1; // count가 중복되는 경우에, mid 값을 1씩 늘려가면서 최대값 찾기
}
}왜 이진 탐색에서는 max = mid - 1을 사용하는가?
- 이진 탐색: 이미 arr[mid] 값을 비교했기 때문에 mid 값을 제외하고 탐색 범위를 줄이기 위해 max = mid - 1을 사용합니다.
- 랜선 자르기 문제: count가 N보다 작다는 것은 현재 mid 길이로는 N개의 랜선을 만들 수 없다는 것을 의미합니다. 따라서 탐색 범위를 줄이기 위해 max를 mid로 설정합니다. 이는 mid 값을 포함하여 그 이하의 길이를 탐색 범위로 설정하는 것입니다. 따라서, -1을 해줄 필요가 없습니다.
Else 문의 의미
- min의 초기값은 0이므로, mid 값은 계속해서 max의 반토막이 될 것입니다.
- 이 문제에서 구해야 할 것은 갯수가 중복될 때의 최대 길이입니다.
- else 조건은 count의 값이 N과 같아질 경우를 의미하고, 이 경우 mid 값을 1씩 늘려가면서 최대 길이를 찾습니다.
요약
- 이진 탐색은 특정 값을 찾기 위해 탐색 범위를 좁혀가는 과정입니다.
- 랜선 자르기 문제에서는 특정 길이로 잘랐을 때의 랜선 개수를 이용해 탐색 범위를 조정합니다.
- Upper Bound개념을 활용하여 중복 원소를 처리합니다.
- max = mid는 탐색 범위를 줄이는 데 사용되며, min = mid + 1은 더 큰 값을 탐색하는 데 사용됩니다.
code
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int Arr[] = new int[N];
long max = 0;
for (int i = 0; i < N; i++) {
Arr[i] = in.nextInt();
if (max < Arr[i]) {
max = Arr[i];
}
}
long min = 0;
long mid = 0;
max++;
while (min < max) {
long count = 0;
mid = (min + max) / 2;
for (int i = 0; i < Arr.length; i++) {
count += (Arr[i] / mid) ;
}
if (count < M) {
max = mid;
} else {
min = mid + 1;
}
}
System.out.println(min-1);
}
}