[BOJ 2230] 수 고르기 (Java, 투포인터)

 

 

 

---

문제 링크

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

2230번: 수 고르기

---

풀이

- 시간복잡도 O(NlogN) = 정렬 O(NlogN) 후 투 포인터 O(N) 수행

- Integer 범위 내이긴 하지만, 초기화시 일부 long 선언 처리

- M 만큼의 차이가 날 때까지 R을 먼저 탐색, A[R] - A[L] > M 조건 성립시 결과값 갱신 (최소값)

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    static int N;

    static long M;

    static long[] A;


    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Long.parseLong(st.nextToken());

        A = new long[N + 1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            A[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() {
        Arrays.sort(A, 1, N + 1); // 오름차순 정렬 필수
        
        int ans = Integer.MAX_VALUE;
        for(int L = 1, R = 1; L <= N; L++) {
            while(R + 1 <= N && A[R] - A[L] < M) { // 주의*
                R += 1;
            }

            if(A[R] - A[L] >= M) {
                ans = Math.min(ans, (int)(A[R] - A[L]));
            }
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}