27.정렬된 배열에서 특정 수의 개수 구하기

📍 문제 설명

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

입력예시

7 2
1 1 2 2 2 2 3

출력예시

4

 

💡 접근

이분탐색을 2번 사용해야한다.

x가 처음으로 나오는 부분의 인덱스와 x가 마지막으로 나오는 부분의 인덱스를 구해야함

 

lt = 0 rt = 7 mid = 3 arr[mid] = 2 >= 2 이므로 rt = mid;

lt = 0 rt = 3 mid = 1 arr[mid] = 1 < 2 이므로 lt = 2

lt = 2 rt = 3 mid = 2 arr[mid] = 2 >= 2 이므로 rt = mid;

 

해당 rt가 2가 처음으로 나오는 인덱스

 

lt = 0 rt = 7 mid = 3 arr[mid] = 2 <= 2 이므로 lt = mid + 1;

lt = 4 rt = 7 mid = 5 arr[mid] = 2 <= 2 이므로 lt = mid + 1;

lt = 6 rt = 7 mid = 6 arr[mid] = 3 > 2 이므로 rt = mid

 

해당 rt가 2가 마지막으로 나오는 인덱스 + 1

 

두 인덱스의 차이가 등장하는 횟수임

👩‍💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int x = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        //x가 등장하는 횟수를 구해야하므로
        //x가 처음 등장할 때의 인덱스와 마지막으로 등장할 때의 인덱스를 빼준다.
        //이분 탐색을 두번 돌린다.
        int lt = 0;
        int rt = n;

        int leftIndex = firstFindX(arr, x, lt, rt);
        int rightIndex = lastFindX(arr, x, lt, rt);

        System.out.println(rightIndex-leftIndex);


    }

    private static int lastFindX(int[] arr, int x, int lt, int rt) {
        while(lt < rt) {
            int mid = (lt + rt) / 2;
            //찾는 값보다 중간 지점의 값이 더 크면 왼쪽 탐색
            if(arr[mid] > x) {
                rt = mid;
            }
            else {
                lt = mid + 1;
            }
        }
        return rt;
    }

    private static int firstFindX(int[] arr, int x, int lt, int rt) {
        while(lt < rt) {
            int mid = (lt + rt) / 2;
            //찾는 값보다 중간 지점의 값이 더 크거나 같으면 왼쪽 탐색
            if(arr[mid] >= x) {
                rt = mid;
            }
            else {
                lt = mid + 1;
            }
        }
        return rt;
    }
}