백준 2230번 수 고르기(자바)

문제 설명

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

제한

1 ≤ N ≤ 100,000

0 ≤ M ≤ 2,000,000,000

0 ≤ |A[i]| ≤ 1,000,000,000

예제 입력 1

3 3 1 5 3

예제 출력 1

4

문제 풀이

처음에는 투포인터로 푸는데 왼쪽을 시작 ,오른쪽을 배열의 끝으로 잡아서 해봤는데 실패했다... 몇몇 수의 차이를 놓치는 것 같아 보였다.

그래서 문득 이것은 시작점을 둘 다 앞에 두고 하는 것이 맞을 것 같다는 생각이 들었고..!!!

시도해보니 성공!!했다..

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];

    for (int i = 0; i < N; i++) {
        arr[i] = Integer.parseInt(br.readLine());
    }

    Arrays.sort(arr);
    int result = Integer.MAX_VALUE;
    int left = 0;
    int right = 1;

    if(M==0){
        System.out.println(0);
        return;
    }

    while (right < N) {
        int diff = arr[right] - arr[left];
        if(diff == M){ //M과 같으면 최소이므로 바로 리턴!
            System.out.println(M);
            return;
        }else if(diff > M){ // M보다 크면서 최소값을 찾기 위해..
            result = Math.min(result,diff);
            left++;
        }else {
            right++;
        }
    }
    System.out.println(result);