완전 탐색 알고리즘 (최근접 점쌍 문제)

최근접 점쌍 문제 (closest pair problem)

여러 개의 1차원의 점을 표준 입력에서 읽은 후, 그 중 가장 가까운 거리에 있는 두 점의 한 쌍을 출력하는 문제이다.

임의조건 : 입력되어지는 숫자들은 공백으로 구분되며, 각각 10자리 이하의 자연수이다.

완전 탐색 알고리즘 (Brute-force algorithm)

최근접 점쌍은 완전 탐색 알고리즘을 사용하면 O(n²)의 시간에 찾을 수 있다. 이를 위해서는 아래와 같이 개의 모든 쌍들 사이의 거리를 계산하여 그 중 가장 가까운 두 점을 고르면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
 
public class test {
    public static void main(String[] args) {
        ArrayList<Integer> numberList = new ArrayList<Integer>();
 
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String input = br.readLine();
            String[] numStrList = input.split(" ");
            for (String numStr : numStrList) {
                numberList.add(Integer.parseInt(numStr));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
 
        Collections.sort(numberList);       //정렬
        Collections.reverse(numberList);    //내림차순 정렬
 
        //완전 탐색 알고리즘
        int minDist = Integer.MAX_VALUE;
        int temp;
        for(int i=0; i<numberList.size()-1; i++){
            for(int j=i+1; j<numberList.size(); j++){
                temp = distance(numberList.get(i), numberList.get(j));
                if (temp < minDist) {
                    minDist = temp;
                    System.out.println("minDist = "+minDist);
                    System.out.println("result = "+numberList.get(i)+", "+numberList.get(j));
                }
                
            }
        }
    }
    
    public static int distance(int p, int q) {
        int dis = p-q;
        return dis;
    }
}
 

결과값

8 34 20 38 27 40
minDist = 2
result = 40, 38