백준>숫자 카드(10815)

❓ 문제

백준 실버5 문제 > 숫자 카드

❗ 해결

보통 배열의 요소 안을 확인하는 문제는 일반적으로 풀었을때 시간초과가 난다.

N = int(input())
card = list(map(int, input().split()))

M = int(input())
deck = list(map(int, input().split()))

for d in deck:
    if d in card:
        print(1, end=' ')
    else:
        print(0, end=' ')

이렇게 간단하게 구현을 하게 되면

보기 좋게 시간초과가 난다 (...)

따라서 이분탐색으로 풀었다.
binary_search()라는 함수를 만들어주고, 파라미터는 배열과 찾는 값을 넣었다.
시작점 (start)은 배열의 가장 첫 번째 요소이고, 끝점(end)는 배열의 가장 마지막 요소이다.

그 후 시작점과 끝점이 동일해 질 때까지 반복문을 돌면서
가운데 지점을 정한다.
(시작 + 끝) / 2를 하면 가운데 지점이 나온다.
찾는 값이 가운데 지점의 값보다 작은 경우 절반의 왼쪽 부분만 확인하고, 반대로 큰 경우 오른쪽 부분만 확인한다.

이렇게 탐색을 하게 되면 단계마다 탐색 범위를 반으로 나누는 것과 동일하므로 시간복잡도는 O(logN)이 된다.

def binary_search(arr, target):

    s = 0
    e = len(arr) - 1

    while s <= e:
        mid = (s + e) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            e = mid - 1
        else:
            s = mid + 1
    return None


N = int(input())
card = list(map(int, input().split()))

M = int(input())
deck = list(map(int, input().split()))

card.sort()

for v in deck:
    if binary_search(card, v) is None:
        print(0, end=' ')
    else:
        print(1, end=' ')

마지막으로 반복문을 돌면서 값을 못찾았으면 0, 찾았으면 1을 출력한다.