[백준 10815번] 숫자 카드

1. 이진 탐색을 활용하여 푼 방법 (1856ms)

n = int(input())
array_n = sorted(list(map(int,input().split())))

m = int(input())
array_m = list(map(int,input().split()))

def binary_search(array,target,start,end):

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

    if array[mid] == target:
      return 1
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1

  return 0

for i in array_m:
  print(binary_search(array_n,i,0,n-1),end=" ")

2. 집합(Set) 자료형을 사용하여 푼 방법 (664ms)

n = int(input())
array_n = list(map(int,input().split()))

m = int(input())
array_m = list(map(int,input().split()))

set_n = set(array_n)

for i in array_m:
  if i in set_n:
    print(1,end=" ")
  else:
    print(0,end=" ")

 

이 문제는 수의 범위가 -1000만 ~ 1000만으로, 단순히 리스트에 in 연산자를 사용하게 되면 시간복잡도 O(N)로 시간초과가 발생하기 때문에 다음과 같은 방법으로 풀이해야 한다 !

 

1. 이진탐색을 활용하여 시간복잡도 O(logN)으로 풀이

2. 집합(Set) 자료형을 사용하여 in 연산자의 시간복잡도 O(1)로 풀이

 

위 결과와 같이 집합 자료형에서 특정 원소가 존재하는지 확인하는 in 연산자를 사용하게 되면, 훨씬 빠르게 풀이할 수 있음을 알 수 있다 :)