[BinarySearch&Counter] 숫자 카드 2

특정 array에 있는 특정 정수의 개수를 구하는 문제이다.

생각해본 방법

    1. Counter 메서드를 사용해서 dict의 key값이 있다면 해당 key의 value를 차례로 출력

    2. BinarySearch를 활용 ( 정확히 어떤식으로 구현해야될지 모르겠음)

 

• Counter는 쉽게 구현가능하다

from collections import Counter
n = int(input())
sang = list(map(int, input().split()))
m = int(input())
array = list(map(int, input().split()))

C = Counter(sang)
for x in array:
    if x in C:
        print(C[x], end=' ')
    else:
        print("0", end=' ')

• BinarySearch로는 어떻게 구현해야할지 모르겠어서 구글링
  • BinarySearch로 하려면 특정한 정수의 연속된 길이를 구하는 부분이 필요하다.
  • BinarySearch를 통해 특정 정수를 발견하면 발견 구간내에서만 count 메서드를 활용해서 찾고자 하는 정수의 개수를 구한다
  • 개수를 구하면 dictionary에 Counter에서 처럼 특정 정수를 key, 특정 정수의 개수를 value로 담는다.
  • 그리고 출력

from sys import stdin
_ = stdin.readline()
N = sorted(map(int,stdin.readline().split()))
_ = stdin.readline()
M = map(int,stdin.readline().split())

def binary(n, N, start, end):
    if start > end:
        return 0
    m = (start+end)//2
    if n == N[m]:
        return N[start:end+1].count(n)
    elif n < N[m]:
        return binary(n, N, start, m-1)
    else:
        return binary(n, N, m+1, end)

n_dic = {}
for n in N:
    start = 0
    end = len(N) - 1
    if n not in n_dic:
        n_dic[n] = binary(n, N, start, end)

print(' '.join(str(n_dic[x]) if x in n_dic else '0' for x in M ))

출처: chancoding.tistory.com/45