[BOJ] 2230번 - 수 고르기 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램

→ 차이를 비교할 두 수가 같은 수일 수도 있고 조건을 만족하는 최솟값을 구해야 한다.

 

두 수의 차이를 구해야하는데 입력된 수열이 정렬되어 있지 않으면 모든 원소끼리 비교해야 한다.

예를 들어 5개의 원소가 있으면 하나의 원소와 나머지 4개의 원소를 모두 비교해보아야 한다.

총 반복되는 횟수는 4 X 3 X 2 X 1 = 24 이다.

4, 2, 1, 3 차이

하지만 이 문제에서 수열의 길이는 최대 100,000까지 가능하기에 시간초과가 뜬다.

모든 원소를 비교하는 방법을 사용했을 때

 

그렇다면 시간을 줄이기 위해 원소를 비교하는 반복 횟수를 줄여야한다.

 

먼저, 수열을 정렬한다.

그러면 아래의 그림과 같이 두 수의 차이가 어떻게 변화할지 예상할 수 있다.

end가 증가할 경우

start가 증가할 경우

위의 그림과 같이 start와 end의 비교할 두 수의 인덱스를 선정하여 비교한다.

• start가 증가하면 자연스럽게 두 수의 차이가 감소한다.
• end가 증가하면 자연스럽게 두 수의 차이가 증가한다.

그러면 이와 같은 성질을 활용하면 start 또는 end가 끝 인덱스에 도달하는 순간 멈추기 때문에 N+N번 이하로 종료될 것이다.

즉, 투 포인터 방식을 사용하기 위해 정렬을 했고 그 결과 반복횟수를 줄일 수 있었다.

---

🍀 풀이 🍀

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

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

        Arrays.sort(array); //오름차순 정렬
        int start = 0;
        int end = 0;
        int result = Integer.MAX_VALUE;
        while(end < n && start < n) {
            int c = array[end]-array[start];
            if(c >= m) { //차이가 클경우
                result = Math.min(result, c);
                start++;
            }
            else { //차이가 작을 경우
                end++;
            }

        }

        bw.write(result+"");
        bw.flush();
        bw.close();
    }
}