(Python/🥈4)백준 알고리즘 10815번: 숫자 카드

문제 출처:https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

풀이:

 

n = int(input())

arr = list(map(int, input().split()))
n2 = int(input())
arr2 = list(map(int, input().split()))

res = []
for i in arr2:
    if i in arr:
        res.append(1)
    else:
        res.append(0)
print(*res)

쉽게 이렇게 풀었지만 시간초과,,

 

n = int(input())

arr = set(map(int, input().split()))
n2 = int(input())
arr2 = list(map(int, input().split()))
print(arr)
print(arr2)
res = []
for i in arr2:
    if i in arr:
        res.append(1)
    else:
        res.append(0)
print(*res)

arr 를 set 함수를 사용하여 받아준다

set 함수 란 아래와 같다.

 

• set 함수는 수학에서 집합과 비슷하다.
• 일반적인 용도는 멤버십 검사, 시퀀스에서 중복제거와 교집합, 합집합, 차집합, 대칭 차집합과 같은 수학 연산을 계산한다.
• 순서가 없는 컬렉션, 원소의 위치나 삽입 순서를 기록하지 않는다.
• 집합은 인덱싱, 슬라이싱 또는 기타 시퀀스와 유사한 동작을 지원하지 않는다.
• python 내장함수로 바로 사용이 가능하다.
• 가장 중요한 특징은 중복을 삭제해준다는 점이다. / 집합은 중복된 데이터를 가지고 있지 않는다!

 

set 함수는 해쉬값을 사용하기 때문에 O(1)이 나온다.

 

출처:https://annajang.tistory.com/38

[Python] set 함수 / python 내장 함수

 

다른 풀이를 보니 이분탐색에 대한 글이 많다. 

def binary_search(num):
    l = 0
    r = N - 1
    while l <= r:
        mid = (l + r) // 2
        if A[mid] == num:
            return 1
        elif A[mid] > num:
            r = mid - 1
        else:
            l = mid + 1
    return 0


for i in B:
    print(binary_search(i), end=' ')

 

출처:

https://eraser-adventure.tistory.com/m/33