[백준] 2230 : 수 고르기 (JAVA)

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

 

[풀이과정]

처음 코드는 완전탐색으로 O(N^2)여서 시간초과가 났다.

투포인터를 사용해서 풀었는데, 먼저 배열을 정렬한 후 계산을 하는 방식이다.

정렬된 상태에서 두 수의 차이를 구하면 이후의 차이가 현재 차이보다 크단 걸 알 수 있으니 넘겨서 더 큰 수끼리 비교하면 된다.

배열 정렬 O(N logN) + 투포인터 탐색 O(N)으로 전체 시간복잡도는 O(N logN)임.

 

이분탐색으로도 풀 수 있고 이분탐색 풀이도 O(N logN)이다.

 

[코드]

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

/*
N개의 수열 A[1], ..., A[N]
두 수를 골랐을 때 차이가 M 이상이면서 제일 작은 경우 구하기
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static long M, result;
    static long[] A;

    public static void main(String[] args) throws IOException {
        init();
        twoPointer();
        /*
        [출력]
        M 이상이면서 가장 작은 차이
         */
        System.out.println(result);
    }

    static void init() throws IOException{
        /*
        [입력]
        1. N, M (1 <= N <= 100,000, 0 <= M <= 2,000,000,000)
        2. 수열 A[i] (0 <= |A[i]| <= 1,000,000,000)
         */
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Long.parseLong(st.nextToken());

        A = new long[N];
        for(int n = 0; n < N; n++){
            A[n] = Long.parseLong(br.readLine());
        }
        //A 오름차순 정렬
        Arrays.sort(A);

        result = Long.MAX_VALUE;
    }

    static void twoPointer(){
        int left = 0;
        int right = 0;

        while(right < N){
            long diff = A[right] - A[left];

            if(diff >= M){
                result = Math.min(result, diff);
                left++;
            }
            else{
                right++;
            }

            if(left == right){
                right++;
            }
        }
    }
}