[알고리즘] Java로 배우는 이진탐색 - feat.백준(숫자 카드 2)

정렬된 배열에서 특정 값의 등장 횟수를 효율적으로 구하는 방법으로 이진탐색을 활용할 수 있다.

 

이진탐색은 정렬된 배열에서 원하는 값을 찾기 위해 검색 범위를 절반으로 줄여나가는 알고리즘이다. 배열에서 중간값을 선택하고, 검색 대상 값이 중간값보다 크거나 작은지에 따라 검색 범위를 좁혀나갈 수 있다. 반복적으로 범위를 줄이다보면 값을 찾거나 값이 존재하지 않음을 확인할 수 있다.

 

이진탐색의 시간복잡도는 O(logN)으로 매우 빠르다.

 

 

이진탐색은 정렬이 된 배열에서 사용해야 하므로 주어진 배열을 우선 정렬해야 한다.

[6, 3, 2, 10, 10, -10, -10, 7, 3] -> [-10, -10, 2, 3, 3, 6, 10, 10, 10]

찾고자 하는 값(target = 10)일 경우 10은 주어진 배열에서 3번 등장한다.

 

 

이진탐색

이진탐색을 두 번 사용하여 등장 횟수를 계산한다.

1. lowerBound : target이 처음 등장하는 위치를 찾는다.
2. upperBound : target보다 큰 값이 처음 등장하는 위치를 찾는다.
3. 등장 횟수는 upperBound - lowerBound로 계산한다.

// 특정 숫자의 등장 횟수를 이진탐색
private static int countOccurrences(int[] nArr, int card) {

    int lower = lowerBound(nArr, card);
    int upper = upperBound(nArr, card);

    return upper - lower;  // tartget의 등장횟수 계산
}

 

 

 

lowerBound

배열에서 target 값이 처음 등장하는 위치를 반환할 메소드이다. 

예를 들면 nArr = [-10, -10, 2, 3, 3, 6, 10, 10, 10]에서 lowerBound(10)은 6을 반환한다.(첫번째 10의 위치)

// target이 처음으로 등장하는 위치 계산
private static int lowerBound(int[] nArr, int target) {
    int left = 0;
    int right = nArr.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nArr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

 

upperBound

배열에서 target보다 큰 값이 처음 등장하는 위치를 반환할 메소드이다. 

예를 들면 nArr = [-10, -10, 2, 3, 3, 6, 10, 10, 10]에서 upperBound(10)은 9를 반환한다.(10이후의 위치)

// target보다 큰 값이 처음으로 등장하는 위치
private static int upperBound(int[] nArr, int target) {
    int left = 0;
    int right = nArr.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nArr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

 

 

 

전체 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nArr = new int[n];

        for (int i = 0; i < n; i++) {
            nArr[i] = sc.nextInt();
        }

        Arrays.sort(nArr);

        int m = sc.nextInt();
        int[] mArr = new int[m];
        for (int j = 0; j < m; j++) {
            mArr[j] = sc.nextInt();
        }

        StringBuilder sb = new StringBuilder();
        for (int card : mArr) {
            int count = countOccurrences(nArr, card);
            sb.append(count).append(" ");
        }
        System.out.println(sb.toString());
    }

    // 특정 숫자의 등장 횟수를 이진탐색
    private static int countOccurrences(int[] nArr, int card) {

        int lower = lowerBound(nArr, card);
        int upper = upperBound(nArr, card);

        return upper - lower;  // tartget의 등장횟수 계산
    }

    // target이 처음으로 등장하는 위치 계산
    private static int lowerBound(int[] nArr, int target) {
        int left = 0;
        int right = nArr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nArr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // target보다 큰 값이 처음으로 등장하는 위치
    private static int upperBound(int[] nArr, int target) {
        int left = 0;
        int right = nArr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nArr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}