백준 10815번 숫자 카드(python)

1. 문제

https://www.acmicpc.net/problem/10815

2. 풀이

문제는 간단하게 2개의 리스트를 만들고 반복문을 돌리며 포함한다면 0을 아니라면 1을 출력하도록 하는 로직을 처음에 짰고 시간초과가 나왔다. 이 시간초과를 해결하기 위해 포함한다에 포인트를 두었다. 2개를 따로 놓았다는 점과 포함한다란 점에서 굳이 여러번 사용할 필요가 없을 수도 있겠다는 생각에 중복을 사용하지 않는 set을 사용해 해결했다.

n = int(input())
card_arr1 = list(map(int, input().split()))

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

for i in card_arr2:
    if i in card_arr1:
        print(1,end=' ')
    else:
        print(0,end=' ')

3. 코드

set을 사용한 방법

n = int(input())
card_arr1 = set(map(int, input().split()))

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

for i in card_arr2:
    if i in card_arr1:
        print(1, end=' ')
    else:
        print(0, end=' ')

이분탐색을 사용해도 가능하다는 점을 알게되어 이분탐색을 통해서도 구현해보았다.

n = int(input())
card_arr1 = list(map(int, input().split()))

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

card_arr1.sort()
def binary_search(arr, target):
    start = 0
    end = len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return False

for i in card_arr2:
    if binary_search(card_arr1, i):
        print(1,end=' ')
    else:
        print(0,end=' ')
        

4. 알게된 점

밑에가 set을 사용한 방법이고 위에가 이분탐색을 사용한 방법이다.

📚 이분 탐색은 처음과 끝 값에서부터 비교를 통해 점점 중간값으로 범위를 좁혀가며 타겟을 찾는 탐색법으로 시간복잡도가 o(m log n)이다.
set은 시간복잡도가 o(1)로 중복이 없다.