[Algorithm] boj_2230 (투포인터)

문제

https://www.acmicpc.net/problem/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

---

접근 방법

• 투포인터로 start = 0, end = 1 부터 차례로 탐색한다.
• 두 수의 차이가 M보다 작으면 end++;
• 두 수의 차이가 M보다 커지면, 해당 수를 최소값으로 초기화시키고 start++;
• end < arr.length 일 동안 탐색한다.

❗️ 주의

• 같은 수일 수 있다.
• M은 0일 수 있다.
• 여기서, start == end인 상황이 나올 수 있다.
  • ex) [1 2 2 3 4], M=1 → start == end 일경우, end++;
    

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj_2230 {

    static int N, M;
    static int[] arr;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];

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

        //sort
        Arrays.sort(arr);

        int start = 0;
        int end = 1;

        while (start < arr.length - 1 && end < arr.length) {
            if (start == end) {
                end++;
                continue;
            }

            int diff = arr[end] - arr[start];

            if (diff < M) {
                end++;
            } else {
                answer = Math.min(answer, diff);
                start++;
            }
        }

        System.out.println(answer);
    }
}