bj1920 수 찾기

음.. 이 문제는 우선 search문제인데 target_card에 해당 숫자가 있는지를 검사하는 문제였어요. 이때 우리는 linear search 또는 binary search를 쓸 수 있는데 input data가 10만개가 들어오는 경우 O(n squared)같은 경우 time out이 나기 때문에 O(nlogn)인 binary search를 써야겠다는 생각을 했어요.

import bisect

n = int(input())
card = list(map(int, input().split()))
card.sort()


def binary_search(ordered_list, target):
    index = bisect.bisect_left(ordered_list, target)

    if index < len(ordered_list) and ordered_list[index] == target:
        return 1
    else:
        return 0


m = int(input())
test = list(map(int, input().split()))
for i in range(m):
    a = binary_search(card, test[i])
    print(a)

bisect module 말고 binary search를 직접 구현한 code도 작성해 보았어요.

n = int(input())
target_list = list(map(int, input().split()))
target_list.sort()


def binary_search(ordered_list, target):
    left, right = 0, len(ordered_list)-1
    while left <= right:
        mid = (left + right) // 2
        if target > ordered_list[mid]:
            left = mid + 1
        elif target < ordered_list[mid]:
            right = mid - 1
        else:
            return 1
    return 0


m = int(input())
finder_list = list(map(int, input().split()))
for i in range(m):
    a = binary_search(target_list, finder_list[i])
    print(a)

아 왜 근데 return 값 말고 yield쓰면 안 되지... 흠...

<generator object binary_search at 0x0000023C54FE15F0>
<generator object binary_search at 0x0000023C54FE15F0>
<generator object binary_search at 0x0000023C54FE15F0>
<generator object binary_search at 0x0000023C54FE15F0>
<generator object binary_search at 0x0000023C54FE15F0>

이렇게 나오는데 integer object가 아닌가 보다..!!
저번에 for loop에 쓴 것을 생각해보면.. iterable한 object인 것 같다