2230 수 고르기

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

2230번: 수 고르기

틀린 이유
투포인터의 범위 증감 방향을 잘못 설정.
정렬했기 때문에 인접한 원소가 가장 작은 차이를 가진다. 따라서 인접한 원소부터
범위를 늘려가면서 최적해를 찾아야 답을 찾을 수 있다.

 

문제 접근

N이 10만이기 때문에 완전탐색은 사용불가능.

차이가 최소인 경우를 찾기 위해 정렬이 필요하다. 차이를 비교하면서 탐색해야 하는데, 이 때 투포인터를 사용하여 인접한 원소가 가장 작은 차이를 갖는건 자명하기 때문에 0, 1 인덱스부터 시작하여 조건을 만족하면 왼쪽의 범위를 줄이고, 만족하지 않으면 오른쪽의 범위를 늘리면서 찾는다.

 

정답 코드

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

public class Main {
    public static void main(String[] args) throws Exception{
      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++){
        st = new StringTokenizer(br.readLine());
        arr[i] = Integer.parseInt(st.nextToken());
      }
      //정렬하고 투포인터로 범위 좁히면서 탐색
      Arrays.sort(arr);
      long answer = arr[arr.length - 1] - arr[0];
      int l = 0, r = 1;
      while(l <= r && r < arr.length){
        long diff = Math.abs(arr[r] - arr[l]);
        if(diff < M){
          r++;
        }
        else{
          l++;
          answer = Math.min(answer, diff);
        }
      }
      System.out.println(answer);
    }
}