[백준] 10816 숫자카드2 Python

https://velog.io/@bellboy/%EB%B0%B1%EC%A4%80-1920-%EC%88%98-%EC%B0%BE%EA%B8%B0-Python

저번에 작성했던 수찾기 코드를 수정을해서 작성하려고 했습니다

import sys
input = sys.stdin.readline

N = int(input())
N_array = list(map(int,input().split()))

M = int(input())
M_array = list(map(int,input().split()))

N_array.sort()

my_array = [ 0 for i in range(M)]

for i in range(M):
    left = 0
    right = len(N_array) -1
    while left <= right:
        middle = (left+right)//2

        if M_array[i] < N_array[middle]:
            right = middle - 1

        elif N_array[middle] < M_array[i]:
            left = middle + 1

        else:
            my_array[i] = 1
            break

for i in my_array:
    print(i)

배열 이진탐색으로는 중복값을 처리하기 힘들어서 딕셔너리를 이용해서 문제를 풀기로했습니다

시간복잡도를 O(NM)에서 O(N+M)으로 만들기전에 먼저 줄일 수 있는 요소들을 찾았습니다
첫번째 sys.stdin.readline
두번째 my_array를 출력하는 구문을 print(" ".join(str(i) for i in my_array))
한번에 출력할 수 있게 줄였습니다
세번째 딕셔너리를 이용해서 문제를 해결했습니다

import sys
input = sys.stdin.readline

N = int(input())
N_array = list(map(int, input().split()))

M = int(input())
M_array = list(map(int, input().split()))

#딕셔너리에 해당 값이 몇개가 있는지 넣어준뒤
count_dict = {}
for num in N_array:
   if num in count_dict:
       count_dict[num] += 1
   else:
       count_dict[num] = 1

#M 배열과 count_dict 키 값이 일치하면 배열에 그대로 넣어줍니다
my_array = []
for num in M_array:
   if num in count_dict:
       my_array.append(count_dict[num])
   else:
       my_array.append(0)

print(" ".join(str(i) for i in my_array))

sort를 사용하지 못할때 시간 복잡도를 줄이는 새로운 방법을 알아냈습니다.