[Python] 백준 #1920- 수 찾기

문제

---

 

1920번: 수 찾기

코드

---

My answer

import sys
input = sys.stdin.readline

n = int(input())
n_list = sorted(list(map(int, input().split())))
m = int(input())
m_list = list(map(int, input().split()))

def binary_search(start, end, target):
    if (start > end):
        return 0
    mid = (start+end)//2
    if (n_list[mid] == target):
        return 1
    elif (n_list[mid] > target):
        return binary_search(start, mid-1, target)
    else:
        return binary_search(mid+1, end, target)

for i in m_list:
    print(binary_search(0, len(n_list)-1, i))

Another answer

# 입력
N = int(input())
A = set(map(int, input().split()))	# 탐색 시간을 줄이기 위해 set으로 받음
M = int(input())
arr = list(map(int, input().split()))

for num in arr:				# arr의 각 원소별로 탐색
    print(1) if num in A else print(0)	# num이 A 안에 있으면 1, 없으면 0 출력

풀이

---

나는 단순하게, 이분탐색으로 구현하여 문제를 해결했다. 중요한 점은 반드시 이분탐색을 하기 위해서는 리스트를 정렬해야한다는 것이다. 

another answer은 탐색대상이 되는 리스트를 set으로 만들고 in을 이용하여 해결하였다. in은 자료형에 따라 시간이 다르기 때문에 문제에 따라 유용하게 사용할 수 있을 것 같다.