[BOJ] 2230. 수 고르기

[작성일]

• 2022-03-15

[분류]

• 투포인터
  
  
  

[문제링크]

• https://www.acmicpc.net/problem/2230
  
  
  

[요구사항]

M 이상이면서 가장 작은 차이를 출력한다.

[풀이]

아주 정석적인 투포인터 문제이다.
우선 배열을 오름차순으로 정렬한다.
이후 i, j 두 개의 포인터를 0부터 시작하도록 둔다.
이제 i와 j를 하나씩 늘려가면서 arr[i]와 arr[j]의 차이를 조건에 맞는지 비교해본다.
차이가 M이면 답이므로 바로 출력하고 종료한다.
M보다 크면 더 작은 차이가 나올 수 있기 때문에 i를 한칸 늘려서 차이를 줄여본다.
M보다 작으면 조건에 만족하지 않아서 차이를 더 벌려야 하기 때문에 j를 한 칸 늘린다.
i <= j 조건을 만족하는 선에서 반복해서 수행하면 정답을 구할 수 있다.

[코드]

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


class Main {
    static int N, M;
    static int[] arr;

    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];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);
        int i = 0, j = 0;
        int ans = arr[N - 1] - arr[0];
        while (j < N && i <= j) {
            int gap = arr[j] - arr[i];
            if (gap < M) {
                j++;
            } else if (gap == M) {
                ans = gap;
                break;
            } else {
                ans = Math.min(ans, gap);
                i++;
            }
        }

        System.out.println(ans);
    }
}