[백준] 4158번 CD 파이썬 코드

코드 1

import sys
input = sys.stdin.readline

while 1:
  n, m = map(int, input().split())
  if n == 0 and m == 0: break
  sangeun = set(int(input()) for _ in range(n))
  sun0 = set(int(input()) for _ in range(m))
  
  cd = sangeun.intersection(sun0)
  print(len(cd))

집합 자료형을 이용해 교집합을 구한 후 그 개수를 세어 답을 구하는 방법. (문제의 조건 중에 중복된 cd가 없다는 것이 있어 가능) 

 

코드 2

import sys
input = sys.stdin.readline

def binary_search(arr, target, start, end):
  if start > end: return 0
  mid = (start + end) // 2
  if arr[mid] == target: return 1
  elif arr[mid] > target: return binary_search(arr, target, start, mid - 1)
  else: return binary_search(arr, target, mid + 1, end)

while True:
  n, m = map(int, input().split())
  if n == 0 and m == 0: break
  sanggeun = [int(input()) for _ in range(n)]
  sun0 = [int(input()) for _ in range(m)]
  total = 0
  for cd in sun0:
    total += binary_search(sanggeun, cd, 0, n - 1)
  print(total)

pypy로 통과한 코드. python에서는 시간초과가 뜸.