ndb-Part3- 이진탐색문제-27 : 정렬된 배열에서 특정 수의 개수 구하기

문제

N 개의 원소를 포함한 수열이 오름차순으로 정렬돼 있다.

수열에서 X가 등장하는 횟수를 계산할 것.

단 시간복잡도 O(logN)알고리즘으로 설계해야 시간초과 판정을 받지 않는다.

입력

• 첫째 줄에 N과 X가 정수 형태로 공백으로 구분돼 입력된다.
  (1<= N <=1,000,000), (-10⁹<=X<=10⁹)
• 둘째 줄에 N개의 원소가정수 형태로 공백으로 구분되 입력된다.
  (-10⁹<=각 원소의 값<=10⁹)

출력

• 수열의 원소중 x인 원소 개수를 출력
• 단 원소가 없다면 -1을 출력

 

예제 입력 1 

7 2
1 1 2 2 2 2 3

예제 출력 1 

4

 

---

 

 

 

Solution

[조건]

• 수열이 오름 차순으로 나열 돼 있다.
• 시간 복잡도를 0(logN)을 이용해야 한다.

[풀이]

• target 의 시작 index와 끝 index를 찾는다.
• 시작 index, 끝 index를 찾는 함수 만들기.

import sys

n, x = map(int, sys.stdin.readline().rstrip().split())
li = list(map(int, sys.stdin.readline().rstrip().split()))


# x가 처음 나온 index 찾기
def find_first_x(data: list, target: int, start: int, end: int):
    if start > end:
        return None

    mid = (start + end) // 2

    # 가장 왼쪽의 target index 를 반환
    if (mid == 0 or data[mid - 1] < target) and data[mid] == target:
        # (target 의 index 가 0부터 시작하는 경우 -> 가장 왼쪽 index 라 볼 수 있음)
        return mid
    # mid 가 가리키는 숫자가 target 보다 크거나 같으면 왼쪽 section 확인
    elif data[mid] >= target:
        return find_first_x(data, target, start, mid - 1)
    # mid 가 가리키는 숫자가 target 보다 작으면 오른쪽 section 확인
    else:
        return find_first_x(data, target, mid + 1, end)


def find_last_x(data: list, target: int, start: int, end: int):
    if start > end:
        return None

    mid = (start + end) // 2

    # 가장 오른쪽의 target index 를 반환
    if (mid == n - 1 or data[mid + 1] > target) and data[mid] == target:
        return mid
    # mid 가 가리키는 숫자가 target 보다 작거나 같으면 오른쪽 section 확인
    elif data[mid] <= target:
        return find_last_x(data, target, mid + 1, end)
    # mid 가 가리키는 숫자가 target 보다 크면 왼쪽 section 확인
    else:
        return find_last_x(data, target, start, mid - 1)


def count_by_value(data: list, target: int) -> int:
    # 1. x가 처음 나온 인덱스 찾기
    first_x_idx = find_first_x(data=data, target=target, start=0, end=n - 1)
    
    # 2. x가 마지막으로 나온 인덱스 찾기
    last_x_idx = find_last_x(data=data, target=target, start=0, end=n - 1)
    
    # target index 가 없으면 -1 출력
    if first_x_idx is None and last_x_idx is None:
        return -1

    return last_x_idx - first_x_idx + 1


count = count_by_value(data=li, target=x)

print(count)