Python : 숫자 카드 2

문제

원본 코드

풀이

• 정렬 + 이분 탐색 + 딕셔너리 문제
• 숫자 카드 N개에서 정수 M개의 각 숫자와 일치하는 값의 개수를 count하여 딕셔너리로 보관한다.
• arr[mid]로 M배열 값을 찾으면서 찾으면 lt와 rt 범위에서 count(target)으로 개수를 구한다.

	- 이분 탐색을 하지 않고 바로 count을 하면 당연히 시간 초과 발생
	n_dic[n] = n_arr.count(n)
    `
    - 탐색 범위를 확줄이고 검색을 해줘야 그나마 시간 초과를 면할 수 있다. 
    return n_arr[lt:rt + 1].count(t)

잡담

• 딕셔너리로 풀어야한다는 생각을 못했다.

전체코드

from sys import stdin

_ = stdin.readline()
n_arr = sorted(map(int, stdin.readline().split()))
_ = stdin.readline()
m_arr = map(int, stdin.readline().split())


def binary(t, lt, rt):
    if lt > rt:
        return 0
    mid = (lt + rt)
    if t == n_arr[mid]:
        return n_arr[lt:rt + 1].count(t)
    elif t < n_arr[mid]:
        return binary(t, lt, mid - 1)
    else:
        return binary(t, mid + 1, rt)


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

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