[JAVA] 배열에서 0에 가장 가까운 숫자 찾기

main

 

Java 배열 내에서 0에 가장 가까운 숫자를 찾아보는 예제를 살펴보겠습니다.

예를들면 [1, -3, 3, -2, 4]에서 0에 가장 가까운 숫자는 1입니다.

0에 가장 가까운 숫자를 효율적으로 찾고 문제 해결을 위한 다양한 기술을 살펴볼 것입니다.

1. 단순 반복문을 사용한 방법

배열을 통한 간단히 반복을 포함하고, 각 요소와 0사이의 절대값를 계산하고, 지금까지 발견된 최소 절대값을 추적합니다.

두 숫자가 0과 동일한 절대값을 갖는 경우, 일관되고 예측 가능한 결과를 보장하기 위해 양수를 우선으로 구하도록 하겠습니다.

public static int findClosestToZero(int[] arr) throws IllegalAccessException {
    if (arr == null || arr.length == 0) {
        throw new IllegalAccessException("Array must not be null or Empty");
    }

    int closest = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if ((Math.abs(arr[i]) < Math.abs(closest)) 
            || ((Math.abs(arr[i]) == Math.abs(closest)) 
            && (arr[i] > closest))) {
            closest = arr[i];
        }
    }
    return closest;
}

 

이 방법은 정수 배열에서 0에 가장 가까운 요소를 찾는 기본적이지만 효과적인 방법을 제공합니다. 시간 복잡도는 O(n)이므로 이문제에 가장 효율적입니다. 

테스트를 통하여 확인해보겠습니다.

@Test
void whenFindingClosestToZero_thenResultShouldBeCorrect() throws IllegalAccessException {
    int[] arr = {1, 60, -10, 70, -80, 85};
    assertEquals(1, FindClosestToZero.findClosestToZero(arr));
}

2. 정렬 및 이진 검색을 사용한 방법

이 방법은 배열을 정렬하여 절대값의 오름차순으로 요소를 정렬하여 문제를 단순화하는 것으로 시작합니다. 정렬 후 이진 탐색 알고리즘을 적용하여 0에 가장 가까운 요소를 효율적으로 찾습니다. 정렬 후 이진 탐색 알고리즘을 적용하여 0에 가장 가까운 요소를 효율적으로 찾습니다. 이진 탐색은 시간 복잡도가 O(log n)로 효율적이지만 정렬 단계에서 O(n log n) 복잡도가 추가되어 전체 시간 복잡도가 O(n log n)이 된다는 점에 유의해야 합니다.

public static int findClosestToZeroWithSortAndBinarySearch(int[] arr) {
    if (arr == null || arr.length == 0) {
        throw new IllegalArgumentException("Array must not be null or Empty");
    }

    // 정렬
    Arrays.sort(arr);
    
    // 이진 검색
    int closestNumber = arr[0];
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (Math.abs(arr[mid]) < Math.abs(closestNumber)) {
            closestNumber = arr[mid];
        }

        if (arr[mid] < 0) {
            left = mid + 1;
        } else if (arr[mid] > 0) {
            right = mid - 1;
        } else {
            return arr[mid];
        }
    }
    return closestNumber;
}

 

이 방법은 입력 배열을 먼저 정렬을 한 이후 이진 검색을 적용하였습니다. 현재 검색 범위의 중간을 확인하고 가장 작은 절대 값을 가진 숫자를 찾기 위해 범위를 점진적으로 줄이면서 확인하고 있습니다.

@Test
void whenFindingClosestToZeroWithSortAndBinarySearch_thenResultShouldBeCorrect() {
    int[] arr = {1, 60, -10, 70, -80, 85};
    assertEquals(1, FindClosestToZero.findClosestToZeroWithSortAndBinarySearch(arr));
}

 

배열 arr의 경우 알고리즘은 먼저 오름차순으로 정렬합니다.([-80, -10, 1, 60, 70, 85])

이 방법은 가장 근접한 수(closesNumber)를 첫 번째 요소인 -80으로 초기화하고 이진 검색을 사용하여 반복합니다. 첫 번째 반복에서 1이 다른 요소보다 0에 더 가깝다는 것을 발견한 후 가장 근접한 수(closesNumber)를 1로 수정합니다. 첫 번째 반복은 또한 원래 배열인 [-80, -10, 1]에서 이 하위 배열을 생성합니다. 이진 검색은 중간 요소를 확인하고 검색 범위를 조정하여 종료될 때까지 1이 0에 가장 가까운지 확인합니다.

3. 우선순위 큐를 사용한 방법

이 방법은 우선순위 큐를 사용하여 전체 배열을 정렬하지 않고도 0에 가장 가까운 숫자를 효율적으로 찾는 방법입니다. 각 숫자를 큐에 추가하고 절대값을 기준으로 가장 작은 숫자만 유지하여 0에 가장 가까운 숫자를 찾습니다.

public static int findClosestToZeroWithPriorityQueue(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0) {
        throw new IllegalArgumentException("Invalid input");
    }

    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Math.abs(b) - Math.abs(a));

    for (int num : arr) {
        pq.offer(num);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

 

Math.abs(b) - Math.abs(a)는 우선순위 큐가저대값에 따라 요소를 정렬하고, 0에서 가장 먼 요소가 가장 낮은 우선순위를 갖도록 합니다. 배열을 반복하면서 각 요소가 우선순위 큐에 추가됩니다. 큐의 크기가 k를 초과하면 0에서 가장 먼 요소가 제거되어 큐가 0에 가장 가까운 k번째 숫자만 유지하도록 합니다. 마지막으로 pq.peek()는 0에 가장 가까운 요소를 반환합니다.

@Test
void whenFindingClosestToZeroWithPriorityQueue_thenResultShouldBeCorrect() {
    int[] arr = {1, 60, -10, 70, -80, 85};
    assertEquals(1, FindClosestToZero.findClosestToZeroWithPriorityQueue(arr, 1));
}

 

이 방법은 우선순위 큐는 0에 가장 가까운 숫자를 나타내는 하나의 요소만 보관하도록 초기화됩니다. 알고리즘 배열 [1, 60, -10, 70, -80, 85]를 반복하면서 각 요소를 순차적으로 처리합니다. 처음에는 큐가 비어 있으므로 1이 추가됩니다. 60은 1보다 0에서 멀리 떠어져 있으므로 추가되지 않습니다. -10이 발생 하면 1이 절대값 면에서 0에 더 가깝기 때문에 추가되지 않습니다. 그 뒤의 요소 70, -80, 85는 모두 -10보다 0에서 멀리 떨어져 있으므로 아무것도 큐에 추가되지 않습니다. 모든 요소를 처리한 큐는 1을 0에 가장 가까운 요소로 유지합니다.

3가지 방법 비교

세가지 방법 모두 Java 배열 내에서 0에 가장 가까운 숫자를 찾는 것을 ㅁ고표로 하지만, 서로 다른 특성을 보입니다.

1. 단순 반복문 방법: 이 문제를 해결하는데 가장 간단하고 효율적이기는 하지만 여러 쿼리가 필요한 경우 점점 비효율적이 됩니다.
2. 정렬 및 이진검색을 활용한 방법: 더 큰 배열에 대해 더 나은 성능을 제공하지만 시간 복잡도는 O(n log n)입니다. 또한 정렬은 메모리 제약 시나리오에서 실행 불가능할 수 있습니다.
3. 우선순위 큐 방식 : 단순성과 성능 간의 균형을 이루므로 가장 가까운 숫자의 하위 집합을 찾는 것만으로 충분하고 배열을 정렬하는 것이 불가능한 시나리오에 적합합니다.

 

 

 

각 용도에 맞는 방법을 선택하여 유사한 문제에 적용하면 좋을 듯 합니다.

 

감사합니다.

 

 

 

 

 

 

 

출처: https://www.baeldung.com/java-array-find-nearest-zero