[백준 / 골드5] 2230 수 고르기 (Java)

문제 보기

사용한 것

• 배열에서 임의의 두 수의 차이가 m보다 클때 가장 작은 경우를 구하기 위한 투포인터

풀이 방법

• N이 10만이므로 O(n^2)은 100억으로 효율성을 통과할 수 없다. 따라서 투포인터로 풀이한다.
• 배열 arr을 오름차순 정렬한다.
• 0번째 인덱스를 l, 1번째 인덱스를 r로 시작하여
  • arr[r] - arr[l]을 diff에 저장한다.
  • diff가 M보다 작으면 r을 1 증가시킨다.
  • diff가 M보다 같거나 크면
    • answer과 비교하여 더 작으면 교체한다.
    • l을 1 증가시켜도 r과 같지 않으면 증가시킨다.
    • 같아지는 경우는 r을 증가시킨다.
• 결국 배열 정렬에 O(n Log n), 투포인터에 O(n)으로 O(n log n)의 시간 복잡도로 통과할 수 있다.

코드

public class Main {

    private static int n;
    private static int m;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        init();
        System.out.println(findMinDiff());
    }

    private static void init() 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());
        }
        br.close();
    }

    private static int findMinDiff() {
        int minDiff = Integer.MAX_VALUE;
        Arrays.sort(arr);
        int l = 0;
        int r = 1;
        while (l < n - 1 && r < n) {
            int diff = arr[r] - arr[l];
            if (diff < m) {
                r++;
            } else {
                minDiff = Math.min(diff, minDiff);
                if (l + 1 == r) {
                    r++;
                } else {
                    l++;
                }
            }
        }
        return minDiff;
    }
}