2230 수고르기 : https://www.acmicpc.net/problem/2230
Problem
Solve
두 수의 차가 M이상이면서 가장 작은 값을 찾는 문제입니다.
이분탐색과 투포인터 두 가지 방법으로 문제를 해결할 수 있습니다.
이분탐색과 투포인터는 모두 정렬된 상태에서 수행해주어야 합니다.
이분탐색
비교해야하는 두 수중 기준점(A)을 반복문을 통해 하나 설정합니다.
기준점과 또 다른 수(B)를 비교하기 위해 B를 이분탐색으로 찾아주는 방법을 사용합니다.
B를 찾기 위해서는 start=A의 인덱스, end = N-1로 선언하고 mid의 값 - A < 두 수의 최소 차(M)인 경우 mid를 더 큰 값으로 비교해주어야합니다. 그렇기 때문에 start = mid+1
그리고 mid값 - A >= M인 경우 더 작은 값을 찾아보기 위해 end = mid로 갱신해줍니다.
여기서 중요한 점은 start==end이 되었을때가 mid - A가 최적의 위치가 된다는 것입니다.
그리고 start==end가 최적의 위치가 되기 위한 조건은 mid-A가 M보다 크거나 같아야 한다는 것입니다.
만약 두 값의 차이가 M보다 작은데 start==end인 경우 최소값으로 바로 갱신해준다면 잘못된 값을 갱신해주게 됩니다. (문제구현하면서 찾는데 오래걸렸던 부분)
Arrays.sort(arr);
int min = Integer.MAX_VALUE;
//기준점
for(int i=0; i<N ; i++){
int start = i;
int end = N-1;
//start가 N이 된다면 더이상 M보다 크거나 같은 값을 만들어 줄 수 없습니다.
while(start<N){
int mid = (start+end)/2;
//두 수의 차가 M보다 작은경우 더 큰 mid를 찾아주기 위해 start = mid+1로 개선
if(arr[mid]-arr[i] < M){
start = mid+1;
}
//두 수의 차가 M보다 크거나 같을때 start==end이면 해당 값(mid)가 최적의 값이 되게 됩니다.
else if(start == end){
min = Math.min(min, arr[mid]-arr[i]);
break;
}
//start!=end라면 더 작은 값을 찾아주기 위해 end=mid
else {
end = mid;
}
}
}투포인터
같은 수를 비교할 수 있기 때문에 start=0, end=0으로 초기화 합니다.
arr[end] - arr[start] < M 인 경우 두 수의 차이를 더 크게 해주어야합니다. 그렇기 때문에 end값을 증가시켜줍니다.
arr[end] - arr[start] >= M인 경우 두 수의 차이가 M을 만족하지만 더 작은 값은 찾기 위해 start값을 증가시켜줍니다.
int start = 0;
int end = 0;
int min = Integer.MAX_VALUE;
//start와 end가 모두 N보다 작은 경우에만 반복합니다.
while(start < N && end < N){
if(arr[end]-arr[start] >= M){
min = Math.min(min, arr[end]-arr[start]);
start++;
}
else{
end++;
}
}Code
이분탐색
import java.io.*;
import java.util.Arrays;
public 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));
String[] NM = br.readLine().split(" ");
int N = Integer.parseInt(NM[0]);
int M = Integer.parseInt(NM[1]);
int[] arr = new int[N];
for(int i=0;i<N;i++){
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int min = Integer.MAX_VALUE;
for(int i=0;i<N;i++){
int start = i;
int end = N-1;
while(start<N){
int mid = (start+end)/2;
if(arr[mid]-arr[i] < M){
start = mid+1;
}
else if(start == end){
min = Math.min(min, arr[mid]-arr[i]);
break;
}
else{
end = mid;
}
}
}
bw.write(String.valueOf(min));
bw.flush();
bw.close();
}
}
투포인터
import java.io.*;
import java.util.Arrays;
public 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));
String[] NM = br.readLine().split(" ");
int N = Integer.parseInt(NM[0]);
int M = Integer.parseInt(NM[1]);
int[] arr = new int[N];
for(int i=0;i<N;i++){
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int start = 0;
int end = 0;
int min = Integer.MAX_VALUE;
while(start<N && end<N){
if(arr[end]-arr[start] >= M){
min = Math.min(min, arr[end]-arr[start]);
start++;
}else{
end++;
}
}
bw.write(String.valueOf(min));
bw.flush();
bw.close();
}
}Result
Reference
