[백준] 1920번: 수찾기(파이썬)

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

아무생각 없이 그냥 찾는 요소가 list안에 있기만 하면 되는 거 아닌가? 라고 생각하여

n = int(input())
num_list_1 = list(map(int,input().split()))
m = int(input())
num_list_2 = list(map(int,input().split()))
for i in num_list_2:
  if i in num_list_1:
    print(1)
  else:
    print(0)

라고 작성하였다.

하지만 어김없이 시간초과

순차탐색은 연산이 너무 많아서 시간 초과가 나기 때문에 이진 탐색으로 풀어야된다고 생각했다.

이틀 전에 이진 탐색 문제로 머리를 꽁꽁 싸맨적이 있어서 이번엔 쉽게 구현할 수 있었다.

n = int(input())
num_list_1 = list(map(int,input().split()))
m = int(input())
num_list_2 = list(map(int,input().split()))
num_list_1.sort()


for search in num_list_2:
  #print(f"찾는 값: {search}")
  i=0
  start = 0
  end = len(num_list_1)-1
  while(start<=end):
    middle = (start+end)//2
    #print(f"중간: {num_list_1[middle]}")
    if search<num_list_1[middle]:
      end = middle-1
    elif num_list_1[middle]<search:
      start = middle+1
    elif num_list_1[middle] == search:
      i=1
      #print("찾았다!")
      break
  if i==1:
    print(1)
  else:
    print(0)

성공~