[BOJ 1920] 수 찾기 파이썬 풀이

1920번: 수 찾기

잘못된 풀이 1 - 시간 초과

def binarySearch(nums, q):
    mid = len(nums)//2
    if nums[mid] == q:
        print(1)
    elif len(nums) == 1:
        print(0)
    else:
        if q < nums[mid]:
            binarySearch(nums[:mid], q)
        else:
            binarySearch(nums[mid:], q)


N = int(input())
nums = list(map(int, input().split()))
nums.sort()
M = int(input())
Qs = list(map(int, input().split()))

for q in Qs:
    binarySearch(nums, q)

 

잘못된 풀이 2 - 런타임 에러

N = int(input())
nums = list(map(int, input().split()))
maxnum = max(nums)
M = int(input())
Qs = list(map(int, input().split()))

hashtable = [0]*(maxnum+1)

for num in nums:
    hashtable[num] = 1

for q in Qs:
    if q>maxnum or hashtable[q]==0:
        print(0)
    else:
        print(1)

 

잘못된 풀이 3 - 시간 초과

N = int(input())
nums = list(map(int, input().split()))
maxnum = max(nums)
M = int(input())
Qs = list(map(int, input().split()))

hashtable = {}

for num in nums:
    index = num%10
    if index in hashtable:
        hashtable[index].append(num)
    else:
        hashtable[index] = [num]

for q in Qs:
    index = q%10
    found = 0
    if index in hashtable:
        for h in hashtable[index]:
            if h == q:
                found = 1
    print(found)

 

맞은 풀이

N = int(input())
nums = list(map(int, input().split()))
M = int(input())
Qs = list(map(int, input().split()))

hashtable = {}

for num in nums:
    index = num%10
    if index in hashtable:
        hashtable[index].append(num)
    else:
        hashtable[index] = [num]

for q in Qs:
    index = q%10
    found = 0
    if index in hashtable:
        for h in hashtable[index]:
            if h == q:
                found = 1
    print(found)