[백준] 10816번 숫자 카드 2(Python - 파이썬)

백준 10816번 문제입니다. (solved.ac)기준 실버 4 문제입니다.

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

가지고 있는 카드가 배열로 주어지고 개수가 궁금한 카드의 번호를 받아 그 카드가 가지고 있는 카드의 배열안에 몇개나 있는지 구하면 되는 간단한 문제입니다. 

 입력값의 범위가 너무커서 당연히 단순 순차탐색은 시간초과 오류가 날것이라고 생각하고 먼저 이진탐색으로 개수를 구해야하는 카드의 아무 아무 인덱스 값을 구하여 그 인덱스로부터 앞뒤로 하나씩 비교하면서 탐색하도록 하였는데 이 방법 또한 시간초과가 발생하였습니다.

 사실 파이썬의 이진 탐색 라이브러리인 bisect를 사용하면 짧고 간단하게 구현이 가능하였지만 이 방법을 사용하지 않고 "이진 탐색", "target의 첫번째 인덱스를 반환해주는 이진탐색", "target의 마지막 인덱스를 반환해주는 이진탐색" 이렇게 세가지 함수를 작성하여 문제를 풀었습니다.

# 이진탐색
def binary_Search(array, target, start, end) :

    # target이 array내부에 없다면 0을 반환
    if start > end :
        return None

    # mid는 중간점
    mid = (start+end)//2

    # 중간점이 target과 일치하면 그 위치 반환
    if array[mid] == target :
        return mid
    elif array[mid] < target :
        return binary_Search(array,target,mid+1,end)
    else :
        return binary_Search(array,target,start,mid-1)

# 이진탐색하여 target이 array내부에 존재한다면
# target의 첫 인덱스를 구함.
def first(array,target,start,end) :

    # target이 array내부에 없다면 0을 반환
    if start > end :
        return None

    # mid는 중간점
    mid = (start+end) // 2

    # 중간점이 target값과 같고 첫번째 인덱스이면 그 위치(mid) 반환
    if (mid == 0 or target > array[mid-1]) and target == array[mid] :
        return mid

    elif array[mid] < target :
        return first(array, target, mid+1, end)
    else :
        return first(array, target, start, mid-1)

# 이진탐색하여 target이 array내부에 존재한다면
# target의 마지막 인덱스를 구함
def last(array, target, start, end) :

    # target이 array내부에 없다면 0을 반환
    if start > end :
        return None

    # mid는 중간점
    mid = (start + end) // 2

    # 중간점이 target값과 같고 마지막 인덱스이면 그 위치(mid) 반환
    if (mid == len(array)-1 or target < array[mid+1]) and target == array[mid] :
        return mid
    elif array[mid] <= target :
        return last(array, target, mid+1, end)
    else :
        return last(array,target,start, mid-1)




import sys
n = int(sys.stdin.readline().rstrip())
# 보유하고 있는 카드들
card = list(map(int, sys.stdin.readline().rstrip().split()))
M = int(sys.stdin.readline().rstrip())
# 개수를 확인하고싶은 카드들
check = list(map(int, sys.stdin.readline().rstrip().split()))

# 이진탐색을 위하여 card를 정렬
card.sort()
ans = 0

for target in  check :

    # 이진탐색을 진행하여 target이 card 내부에 있으면
    # target의 개수를 구해야하니
    # ans에 마지막 인덱스 - 첫번째 인덱스 + 1을 저장
    if (binary_Search(card,target,0,n-1) != None):
        ans = last(card,target,0,n-1) - first(card,target,0,n-1) + 1

    print(ans, end=' ')
    # ans값 초기화
    ans = 0