백준 2230번(Java)

문제는 다음과 같다.

자세한 건 직접 가서 보자.

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

브루트 포스로 풀기에는 크기가 너무 크고 반복해야 하는 횟수도 많다.

그렇다면 다른 방법으로 접근해야 한다.

그게 무엇이냐?

투포인터다.

먼저 입력받은 배열을 오름차순으로 정렬한 다음 진행한다.

이 문제에서 투포인터를 사용할 때 조건은 다음과 같다.

1. r < n 보다 작아야 가장 큰 수에 도달했을때 다른 모든 값들과 뺄셈을 할 수 있다.

2. arr[r] - arr[l] < m 보다 작으면 조건이 성립하지 않으므로 r을 증가시켜 더 큰 수와 뺄셈이 되도록 한다.

3. arr[r] - arr[l] == m 일 시 가장 작은 차이를 찾았으니 더 이상 진행할 필요없다.

4. 그 외는 별개로 두 값의 차이를 계산하여 가장 작은 값을 저장하고 l을 증가시키다.

이 과정이 끝나면 결과를 얻을 수 있다.

코드를 보자.

public class Main {
    static int n, m;
    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());

        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(br.readLine());

        Arrays.sort(arr);

        int r = 0;
        int l = 0;
        int answer = Integer.MAX_VALUE;
        while(r < n){
            if(arr[r] - arr[l] < m){
                r++;
                continue;
            }
            else if(arr[r] - arr[l] == m){
                answer = m;
                break;
            }

            answer = Math.min(answer, arr[r] - arr[l]);
            l++;
        }

        System.out.println(answer);
    }
}

끝!