[BOJ] [Python] 10815번 : 숫자 카드

M개의 수에 대해서, 상근이가 가진 숫자 카드와 비교하는 문제이다. 

중복되는 수가 있다면 1, 없다면 0이다.

 

순차 탐색으로 풀었다.

 

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

m = int(input())
tmp = list(map(int, input().split()))
B = sorted(set(tmp))

idx = 0

result = {}


for num in B:
    while True:
        if idx == n:
            result[num] = 0
            break

        if num == A[idx]:
            result[num] = 1
            break

        elif num < A[idx]:
            result[num] = 0
            break

        else:
            idx += 1

for n in tmp:
    print(result[n], end=" ")

 

수기 설명

 

아래 수가 작거나 상근이의 수와 같으면, B의 index를 높여주고,

상근이가 가진 수가 작으면, A의 index를 높여준다.

 

index가 M이 됐을 때 멈춘다.

따라서, 시간 복잡도는 O(M)이다. 

 

 

 

이진탐색으로도 풀어보자.

 

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

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


def BSearch(target):
    low = 0
    high = len(A) - 1

    while low <= high:
        mid = (low + high) // 2

        if A[mid] == target:
            print("1", end=" ")
            return

        elif A[mid] < target:
            low = mid + 1

        else:
            high = mid - 1

    print("0", end=" ")
    return


for num in B:
    BSearch(num)

 

시간복잡도는 O(log₂M)이다.

 

M이 32일 경우, 이진탐색이 약 6배 빠르다.

이 문제처럼 N이나 M이 클 경우에는, 이진탐색이 더 나은 방법인 것 같다.