10816번 숫자카드2

문제링크 : www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

---

---

<알고리즘>

  1) N, N개의 숫자 목록, M, M개의 target목록 입력받기

  2) N개의 숫자목록은 각각의 요소가 몇개인지 counter로 확인, 중복을 제거하고 오름차순으로 정렬하기

  3) 0~M-1까지의 target목록을 돌면서 N개의 숫자목록에 해당 숫자가 있는지 확인

    => 이분탐색을 이용하여 확인(배열의 left, right, mid를 지정하고 mid값과 target값 비교하는 재귀함수)

  4) 존재한다면 앞서 counter함수를 이용해 세어놓은 딕셔너리를 통해 value값을 결과값 배열에 입력

     존재하지 않는다면 i번째 결과값 배열=0이 됨

 

 

 

 

 

메모리 : 135096KB    시간 : 4420ms

def isIt(numbers, left,right, mid, target):
    if(numbers[mid]<target):
        if(left==mid or right==mid):
            return -1
        return isIt(numbers, mid,right,(mid+right)//2,target)
    elif(numbers[mid]>target):
        if (left == mid or right == mid):
            return -1
        return isIt(numbers,left,mid,(left+mid)//2,target)
    elif(numbers[mid]==target):
        return mid
import sys
from collections import Counter
N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
#같은 수가 몇개씩 있는지 count
counterNumbers = Counter(numbers)
#중복을 없애고 오름차순으로 정렬
numbers = sorted(list(set(numbers)))

M = int(sys.stdin.readline())
targetN = list(map(int,sys.stdin.readline().split()))
howmany = [0 for _ in range(M)]

for i in range(M):
    if(targetN[i]>numbers[len(numbers)-1] or targetN[i]<numbers[0]):
        howmany[i] = 0
    elif (targetN[i]==numbers[len(numbers)-1]):
        howmany[i] = counterNumbers[numbers[len(numbers)-1]]
    elif(targetN[i]<numbers[0]):
        howmany[i] = counterNumbers[numbers[0]]
    else:
        result = isIt(numbers, 0,len(numbers)-1,(len(numbers)-1)//2,targetN[i])
        if(result != -1):
            howmany[i] = counterNumbers[numbers[result]]

for item in howmany:
    print(item, end= " ")