BOJ - 수 고르기

leehyunjon·2022년 12월 15일
0

Algorithm

목록 보기
141/162

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

https://steady-coding.tistory.com/60

profile
내 꿈은 좋은 개발자

0개의 댓글