배열에서 특정 수의 개수 구하기

* Binary Search 활용하기

이진 탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법

✅ 문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요.
단, 이 문제의 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력 예시
7 2
1 1 2 2 2 2 3

출력 예시
4

💻 코드

import java.util.*;

public class BinarySearchEx2
{
    public static int lowerBound(ArrayList<Integer> a, int target, int start, int end) {
        while (start < end) {
            int mid = (start + end) / 2;
            if (a.get(mid) >= target) end = mid;
            else start = mid + 1;
        }
        return end;
    } // 낮은 범위 내 숫자 검색 이후

    public static int upperBound(ArrayList<Integer> a, int target, int start, int end) {
        while (start < end) {
            int mid = (start + end) / 2;
            if (a.get(mid) > target) end = mid;
            else start = mid + 1;
        }
        return end;
    }

    public static int countByRange(ArrayList<Integer> a, int leftValue, int rightValue) {
        int size = a.size();
        int rightIndex = upperBound(a, rightValue, 0, size);
        int leftIndex = lowerBound(a, leftValue, 0, size);
        return rightIndex - leftIndex;
    } // 인덱스 차이 값 반납 (개수 구하기)

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int x = sc.nextInt();
        sc.nextLine(); // 버퍼 삭제

        ArrayList<Integer> arrayList = new ArrayList<>();
        for(int i = 0; i < n; i++)
        {
            int tmp = sc.nextInt();
            arrayList.add(tmp);
        }
        Collections.sort(arrayList); // 입력 값 오름차순 정렬
        int cnt = countByRange(arrayList, x, x); // 결과 값을 입력 받기
        if (cnt == 0) System.out.println(-1);
            //  값이 x인 원소가 존재한다면
        else System.out.println(cnt);
    }

}

📝 정리

lowerBound : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
upperBound : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
시간 복잡도 : O(logN)