백준 - 2230 수 고르기(Java)

투포인터 문제입니다.

 

n개의 숫자 중 두 개의 숫자를 고를 때, 두 수의 차이가 m이상이면서 최소가 되는 경우를 구해야합니다.

문제 접근 순서는 다음과 같습니다.

1. 입력 값을 정렬한다.
2. 두 개의 포인터(lp, hp)를 움직여 차이를 구한다.
   1. 초기 위치는 lp=0, hp=1이다.
   2. lp, hp위치의 값 차이가 m보다 크면 차이를 줄인다. (lp를 앞으로 움직인다.)
   3. lp, hp위치의 값 차이가 m보다 작으면 차이를 늘린다. (hp를 앞으로 움직인다.)
   4. lp가 n-1에 도달할 때 까지 반복한다. (hp가 n에 도달하고, lp가 n-1까지 도달하는 경우이다.)
3. 저장된 최소 차이를 출력한다.

 

 

[구현 코드]

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(stz.nextToken());
        int m = Integer.parseInt(stz.nextToken());

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

        // 정렬
        Arrays.sort(arr);

        // 이동할 포인터
        int lp = 0;
        int hp = 1;

        // 정렬 되어있기 때문에, 양쪽 끝의 차이가 최대 차이임
        int answer = arr[n - 1] - arr[0];

        // lp가 끝에 도달할 때 까지 반복
        while (lp < n - 1) {
            // 차이
            int differ = arr[hp] - arr[lp];

            // 차이가 m 이상
            if (differ >= m) {
                // 최소 차이를 갱신한다.
                if (differ < answer) {
                    answer = differ;
                }
            }

            // hp가 끝까지 도달하면 lp를 늘려나감
            if (hp == n - 1) {
                lp++;
                continue;
            }

            // 차이가 m보다 크므로 lp를 늘려 차이를 줄임
            if (differ > m) {
                lp++;
            } else {
                hp++;
            }
        }

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }
}