📍백준 #4158

❗틀렸습니다

n, m = map(int, input().split())

array1 = [int(input()) for _ in range(n)]
array2 = [int(input()) for _ in range(m)]

cnt = 0
for i in array2:
  start = 0
  end = n - 1
  while start <= end:
    mid = (start + end) // 2
    if array1[mid] == i:
      cnt += 1
      break
    elif array1[mid] < i:
      start = mid + 1
    else:
      end = mid - 1

print(cnt)

위와 같은 코드를 작성하고 비슷한 코드로 여러 번 제출을 했는데 모두 틀렸다는 결과가 나왔다.
문제를 다시 차근차근 읽어보니 첫 문장에 '입력은 여러 개의 테스트 케이스로 이루어져 있다.' 라고 쓰여 있었다. 그리고 마지막 문장에 '입력의 마지막 줄에는 0 0이 주어진다.'라고 쓰여있었다.
n과 m을 한 번만 입력 받는 것이 아니라 반복문으로 여러 개의 테스트 케이스를 입력받고 0 0이 입력되면 종료하는 조건을 작성해야 한다는 것을 알 수 있었다.

❗시간 초과

while True:
  n, m = map(int, input().split())
  if n == 0 and m == 0:
    break
    
  array1 = [int(input()) for _ in range(n)]
  array2 = [int(input()) for _ in range(m)]

  cnt = 0
  for i in array2:
    start = 0
    end = n - 1
    while start <= end:
      mid = (start + end) // 2
      if array1[mid] == i:
        cnt += 1
        break
      elif array1[mid] < i:
        start = mid + 1
      else:
        end = mid - 1

	print(cnt)

코드를 수정했는데 시간 초과 오류가 발생했다.

import sys

while True:
  n, m = map(int, sys.stdin.readline().split())
  if n == 0 and m == 0:
    break
    
  array1 = [int(sys.stdin.readline()) for _ in range(n)]
  array2 = [int(sys.stdin.readline()) for _ in range(m)]

  cnt = 0
  for i in array2:
    start = 0
    end = n - 1
    while start <= end:
      mid = (start + end) // 2
      if array1[mid] == i:
        cnt += 1
        break
      elif array1[mid] < i:
        start = mid + 1
      else:
        end = mid - 1
  print(cnt)

이전 게시물의 문제를 풀면서 알게된 sys 라이브러리의 sys.stdin.readline() 함수를 이용해 input 시간을 줄였는데도 시간 초과 오류가 다시 발생했다.

🌟 집합 자료형 이용

import sys

while True:
  n, m = map(int, sys.stdin.readline().split())
  if n == 0 and m == 0:
    break
    
  array1 = set(int(sys.stdin.readline()) for _ in range(n))
  array2 = [int(sys.stdin.readline()) for _ in range(m)]

  cnt = 0
  for i in array2:
    if i in array1:
      cnt += 1
  print(cnt)

오늘 이진 탐색을 구현하면서 여러가지 방법 중 하나로 집합 자료형을 이용한 코드가 떠올라 집합을 사용해서 array2 리스트에 있는 데이터가 집합 array1에 있으면 cnt를 증가시키는 방법으로 코드를 수정했다.
수정 결과 맞았습니다!!가 나왔다.

🧐 Why?

왜 집합 자료형을 쓰기 전 코드에서 시간 초과 오류가 발생했을까?

아직 답을 찾지 못했다.
다른 사람들의 코드를 보면서 공부해야겠다.

몇몇 사람들의 코드에 defaultdic가 쓰여 있었다.
dictionary에서 존재하지 않는 키를 조회할 경우 KeyError exception이 발생하는데 
defaultdict은 존재하지 않는 키를 조회하면 설정한 디폴트 값을 기준으로 해당 키에 대한 아이템을 dictionary에 추가해준다.