2230번: 수 고르기(Java)

 투 포인터를 사용해 해결할 수 있다. 우선, 필요한 변수들을 선언한다. 

int N, M;
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
M = scanner.nextInt();
int[] arr = new int[N];
int p1 = 0;
int p2 = 0;
int result = 2000000000;

|A[i]|의 범위가 0~1000000000 이므로, 두 수의 차이는 최대 2000000000까지 될 수 있다. 따라서 result를 우선 2000000000로 설정했다.

 

 

 

arr에 데이터를 넣어 주고, 투 포인터를 사용해야 하기 때문에 arr를 정렬해준다. 

Arrays.setAll(arr, i -> scanner.nextInt());
Arrays.sort(arr);

 

 

 이제 문제에 대해 생각해야 한다. 투 포인터를 사용해 O(n)으로 끝내야 한다. 우선 while문은 p1 < N && p2 < N일때 반복한다. 

 정렬된 배열이므로, p2 - p1이 M보다 크거나 같은 순간, p1++을 해 주고, result를 갱신하면 된다. 그게 아니라면 p2++을 통해 2번째 포인터를 증가시켜주면 된다. 마지막으로 result를 출력해주면 된다.

while(p1 < N && p2 < N){
    int sub = arr[p2] - arr[p1];
    if(sub >= M){
        result = Math.min(result, sub);
        if(result == M){
            break;
        }
        p1++;
    }
    else{
        p2++;
    }
}
System.out.println(result);

 

 

 

 

 

 

 

결과 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int N, M;
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        int[] arr = new int[N];
        int p1 = 0;
        int p2 = 0;
        int result = 2000000000;
        Arrays.setAll(arr, i -> scanner.nextInt());
        Arrays.sort(arr);
        while(p1 < N && p2 < N){
            int sub = arr[p2] - arr[p1];
            if(sub >= M){
                result = Math.min(result, sub);
                if(result == M){
                    break;
                }
                p1++;
            }
            else{
                p2++;
            }
        }
        System.out.println(result);
    }
}