문제 정리

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어있다.

이 수열에서 x가 등장하는 횟수를 계산하라.

arr = [1, 1, 2, 2, 2, 2, 3]
x = 2

>>> 4

접근 방법

이 문제는 N(logN)으로 풀어야 한다.

따라서 이진 탐색을 사용해야하는데, bisect 모듈을 사용하였다.

수열에서 x가 처음 등장하는 왼쪽 index와 마지막에 등장하는 오른쪽 인덱스를 찾아서

수열에 인덱스 슬라이싱으로 출력하면 될것 같다고 생각했다.

코드 진행

먼저 입력 값을 받아와서 수열을 생성해주었다.

import bisect
import sys

def input():
    return sys.stdin.readline().strip()

n, x = map(int, input().split())
arr = list(map(int, input().split()))

bisect 모듈의 bisect_left, bisect_right를 사용해서 왼쪽 index와 오른쪽 index를 찾는다.

# x의 값을 arr에서 이진탐색으로 찾는다.
# 왼쪽 인덱스와 오른쪽 인덱스를 찾아서 슬라이싱한다.
left_index = bisect.bisect_left(arr, x)
right_index = bisect.bisect_right(arr, x)

아래 조건들을 추가하고 인덱스 슬라이싱으로 출력한다.

(1) 이진검색값 왼쪽 인덱스가 배열 안에 있어야 한다. (2) 이진검색값 오른쪽 인덱스가 배열 안에 있어야 한다. (3) 왼쪽 오른쪽 인덱스가 찾는 값이랑 일치해야한다.