특정 조건의 값(배열에 없는, 선택할 떄?) - 이진탐색
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ;
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
String [] Strarr = br.readLine().split(" ");
int[] Narr = new int[N];
int sumNarr = 0 ;
for(int i =0; i<N; i++)
{
Narr[i] = Integer.parseInt(Strarr[i]);
sumNarr+=Narr[i];
}
Arrays.sort(Narr);
int M = Integer.parseInt(br.readLine());
if(sumNarr<M)
{
bw.write(String.valueOf(Narr[N-1]));
bw.flush();
bw.close();
}
else{
int start = 0 ;
int end = Narr[N-1];
int result = 0 ;
int sumcnt = 0 ;
while(start<=end)
{
int mid = (start+end)/2;
sumcnt = 0;
//탐색 범위 설정
for(int val: Narr)
{
if(val<mid)
{
sumcnt+=val;
} else{
sumcnt+=mid;
}
}
if (sumcnt>M) //판별에 따른 탐색 범위 설정
{
end =mid-1;
} else {
result = mid;
start = mid +1;
}
}
bw.write(String.valueOf(result));
bw.flush();
bw.close();
}
}
}
1. 이진 탐색
(일단 정렬 -> 조건에 따라 start ,end를 정해주고 mid 값을 도출)
2. start ,end를 재조정할 기준을 계산
3. start, end재조정에 따라서 mid 값 계산 후 특정 범위 (start =mid+1 or end = mid-1)