[백준] 2230 : 수 고르기 - Java

이지연·2026년 1월 4일

투포인터

코딩테스트 풀이(구현, 자료구조, 알고리즘)

목록 보기

39/50

백준 문제 URL

문제 요약

수열에서 두 수의 차이가 m 이상이면서,
그 차이값이 최소가 되는 두 수의 차이를 구하는 문제다.

즉,

배열 arr에서 arr[i] - arr[j] >= m (i > j)을 만족하는
최소 (arr[i] - arr[j]) 값을 찾는다.

핵심 아이디어

이 문제는 단순히 모든 쌍을 비교하면 (O(n^2))이 되므로,
정렬 + 슬라이딩 윈도우 투 포인터를 사용한다.

핵심은 고정된 오른쪽 포인터(i) 기준으로 왼쪽 포인터(start)를 이동시키는 방식:
1. 배열을 정렬한다.
2. 오른쪽 포인터(i)를 고정하고,
3. 왼쪽 포인터(start)를 이동시켜 조건 arr[i] - arr[start] >= m을 만족하는
최소 차이값을 갱신한다.

알고리즘 핵심 로직

1. 배열 정렬 (오름차순)
2. start = 0, minDiff = 무한대
3. for i = 0 to n-1:
   while (arr[i] - arr[start] >= m):
       minDiff = min(minDiff, arr[i] - arr[start])
       start++

핵심:

arr[i] - arr[start] < m 이면 윈도우를 좁히지 않고 다음 i로 이동
조건을 만족하면 minDiff 갱신 후 start++로 윈도우 축소

전체 코드 (제출용)

package A6투포인터.BaekJoon;

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

public class G2230수고르기 {
    public static void main(String[] args) throws IOException {
        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 minDiff = Integer.MAX_VALUE;
        int startIdx = 0;

        for (int i = 0; i < n; i++) {
            while (startIdx <= i && arr[i] - arr[startIdx] >= m) {
                minDiff = Math.min(minDiff, arr[i] - arr[startIdx]);
                startIdx++;
            }
        }

        System.out.println(minDiff);
    }
}