[이코테] CH07 이진 탐색 실전문제 27번 정렬된 배열에서 특정 수의 개수 구하기

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def findElem(x):
    n = len(arr)
    a = findFirstElem(0,n-1)
    b = findSecondElem(0,n-1)
    if a == None:
        return 0
    else:
     return b-a+1
def findFirstElem(start,end):
    
    if start > end:
        return None
    mid = (start + end) // 2
    if (mid == 0 or x > arr[mid-1]) and arr[mid] == x:
        return mid
    elif arr[mid] >= x:
        return findFirstElem(start,mid-1)
    else:
        return findFirstElem(mid+1,end)
def findSecondElem(start,end):
    
    if start > end:
        return None
    mid = (start + end) // 2
    if (mid == len(arr)-1 or x < arr[mid+1]) and arr[mid] == x:
        return mid
    elif arr[mid] > x:
        return findSecondElem(start,mid-1)
    else:
        return findSecondElem(mid+1,end)


    
N,x = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

count = 0
Value = findElem(x)
if Value == 0:
    print(-1)
else:
    print(Value)

이거 문제 너무 어렵다...

처음 끝 인덱스 빼서 구해야겠다 싶었는데

그 로직을 짜려니까 너무 어려웠다

 

아직도 의문인건

firstindex에선 등호를 , 두번째에선 왜 등호를 안 붙이는지에 대해서

잘 이해가 안 된다

다른 문제들 풀고 다시 돌아오기..

+

이런 좋은게 있었다니

역시 코테는 .. 실력도 실력이지만 자주 문제를 풀어보고 라이브러리 익히는것도 중요한 것 같아요

이진 탐색 라이브러리 bisect를 알고있다면 5분컷 문제였네요

 

라이브러리도 잘 사용할 줄 알아야겠다

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
from bisect import bisect_left,bisect_right

def count_by_range(arr,left_value,right_value):
    right_index = bisect_right(arr,right_value)
    left_index = bisect_left(arr,left_value)
    return right_index - left_index 


    
N,x = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

count = 0
Value = count_by_range(arr,x,x)
if Value == 0:
    print(-1)
else:
    print(Value)