백준 1920번 파이썬

문제에서 보듯이 리스트안에 찾고자하는 값이 있는지 없는지만 리턴해주면 된다
당연히 처음 생각할 수 있는 방법은 순찬탐색이다 순차탐색을 진행해 준다면 한번을 찾는데 시간복잡도는 O(n)이들고 M번을 찾아야하므로 O(N^2)이 되고 최대 연산횟수는 10만의 제곱인 100억 번이여서 아마 순차 탐색으로는 time error가 발생하게 될 것이다. 따라서 순차 탐색으로 먼저 제출해 봤다.

#입력
#첫째줄 입력받고자하는 리스트의 크기 N
#둘째줄 리스트값들을 공백으로 구분하여 입력
#셋째줄 찾고자하는 값들의 개수 M
#넷째줄 찾고자하는 값들의 공백으로 구분하여 입력
import sys
N = int(sys.stdin.readline())
input_list = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())

search_list = list(map(int, sys.stdin.readline().split()))

for i in range(M):
  flag = 0
  for j in range(N):
    if input_list[j] == search_list[i]:
      print(1)
      flag = 1
      break;
  if(flag == 0):
    print(0)

역시나 결과는

따라서 시간복잡도가 O(logN)인 이진 탐색으로 탐색을 해봤다.

#입력
#첫째줄 입력받고자하는 리스트의 크기 N
#둘째줄 리스트값들을 공백으로 구분하여 입력
#셋째줄 찾고자하는 값들의 개수 M
#넷째줄 찾고자하는 값들의 공백으로 구분하여 입력
import sys

def Bsearch(list, size, target):
  start = 0
  end = size - 1

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

    if(list[mid] == target):
      return True
      break
    elif(list[mid] > target):
      end = mid - 1
    else:
      start = mid + 1

  return None

N = int(sys.stdin.readline())

input_list = list(map(int, sys.stdin.readline().split()))
input_list.sort()
M = int(sys.stdin.readline())

search_list = list(map(int, sys.stdin.readline().split()))

for i in range(M):
  if Bsearch(input_list, N, search_list[i]) == None:
    print(0)
  else:
    print(1)
  

결과는 맞았다.