[BOJ] 2230 수 고르기 - JAVA

1. 문제

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이 된다.

---

2. 풀이

1.  배열을 정렬한다.

2.  |A[i]| ≤ 1,000,000,000이므로 min값을 2,000,000,000으로 설정한다.

3.  같은 수를 고를 수도 있으므로 l = 0, r = 0으로 두고 시작한다.

4.  만약 두 수의 차이가 M보다 작다면 ++r한다. 또, +1한 r이 N과 같다면 인덱스 오류를 막기위해 반복을 종료한다.

5.  만약 두 수의 차이가 M보다 크다면 l++하고 diff와 min 중 최솟값을 min에 저장한다.

6.  5.에서, 바뀐 min이 M과 동일하다면 반복을 종료한다.

7.  탐색이 끝나면 min을 출력한다.

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

public class BOJ_2230_수고르기 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.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++) arr[i] = Integer.parseInt(in.readLine());
      Arrays.sort(arr);

      int min = 2000000000;
      int l = 0,r = 0,diff;
      while(l<=r){
         diff = arr[r]-arr[l];
         if(diff<M) {
            if(++r == N) break;
         }
         else {
            l++;
            min = Math.min(min,diff);
            if(min==M) break;
         }
      }

      System.out.println(min);
   }
}

---

3. 결과

오.. 자꾸 11퍼센트에서 틀려서 로직에 문제가 있나 열심히 봤는데 답은 그냥.. min 변수의 초기화 문제였다.

M의 최댓값으로 지정했는데 생각해보니 diff의 최댓값으로 지정해야했다.