[Python] 4158번 CD

✏️ 문제

문제 파악

 

 

알고리즘

• 자료 구조
• 해시를 사용한 집합과 맵
• 두 포인터
• 이분 탐색

 

 

코드

• 이분 탐색으로 풀려니까 자꾸 시간초과가 떠서 결국 pypy3로 제출 ㅠ

import sys
input = sys.stdin.readline

while True:
  n, m = map(int, input().split())
  if n == 0 and m == 0:
    break

  n_number = [int(input()) for _ in range(n)]
  m_number = [int(input()) for _ in range(m)]
  cd = 0

  for i in range(m):
    start, end = 0,  n-1

    while start <= end:
      mid = (start+end) // 2

      if n_number[mid] == m_number[i]:
        cd += 1
        break
      elif n_number[mid] > m_number[i]:
        end = mid - 1
      elif n_number[mid] < m_number[i]:
        start = mid + 1
  print(cd)

 

• 이분 탐색으로 말고 집합으로 푸는 방법

import sys
input = sys.stdin.readline

while True:
  n, m = map(int, input().split())
  n_number = {int(input()) for _ in range(n)}
  m_number = {int(input()) for _ in range(m)}

  if n == 0 and m == 0:
    break
  
  print(len(n_number & m_number)) # 교집합