[백준 2230] 수 고르기 자바(Java) 풀이

문제 링크 : https://www.acmicpc.net/problem/2230

2230번: 수 고르기

 

[ 문제 ]

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

 

[ 입력 ]

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

 

[ 출력 ]

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

 

[ 예제 입력 1 ] 

3 3
1
5
3

[ 예제 출력 1 ] 

4

 

[ 풀이 ]

투 포인터를 사용하면 되는 문제였습니다. 이분 탐색으로 풀어 보려고 했지만, 마땅히 떠오르는 방법이 없어 투 포인터로 해결했습니다.

 

[ 결과 ] 

 

[ 정답 코드 ]

import java.util.*;
import java.io.*;
public class Main{
   static int[] arr;
   static int N;
   static int M;
   static int min = Integer.MAX_VALUE;
   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());
      arr = new int[N];

      for (int i = 0; i < N; i++) {
         arr[i] = Integer.parseInt(br.readLine());
      }
      Arrays.sort(arr);

      int start = 0;
      int end = 0;

      while(end<N){
         if(arr[end] - arr[start] < M){
            end++;
         }
         else if(arr[end] - arr[start] > M){
            min = Math.min(arr[end] - arr[start], min);
            start++;
         }
         else {
            min = M;
            break;
         }
      }

      System.out.println(min);


   }
}