실버 5

문제

해당 문제 링크

정답 - 이진탐색

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

def binary(arr, value):
    left, right = 0, n-1

    while left <= right:
        mid = (left+right)//2

        if arr[mid]==value:
            return 1
        if arr[mid]>value:
            right=mid-1
        else:
            left=mid+1
    return 0

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

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

a.sort()
for i in b:
    print(binary(a, i), end= ' ')

정답 - 집합

input()
n=set(map(int, input().split()))
input()
m=list(map(int, input().split()))
for i in m:
    if i in n:
        print(1, end=' ')
    else:
        print(0, end=' ')

풀이

처음 풀이는 단순하게 for문으로 돌렸는데 런타임 에러가 났다.

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

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

print(a)
print(b)

res=[]
for i in range(m):
    if b[i] in a:
        res.append(1)
    else:
        res.append(0)

print(*res)

알고리즘 분류의 이진 탐색이 있길래 이진 탐색으로 작성했다.
(for문으로 돌리기 전에 미리 이진 탐색으로 돌릴걸이라는 아쉬움이 있었다.)

하지만 그럼에도 계속 런타임 에러가 나서 코드 참고하며 하나씩 바꾸니까 이진 탐색에서 right부분을 len(arr)로 안하고 n-1로 했더니 정답 처리가 되었다..
그래서 len()함수에 대해 시간 복잡도를 알아볼까 한다.
len() 함수는 O(1)의 시간복잡도를 갖는다. 엥..그럼에도 입력해놓은 값이 존재하기 때문에 n의 값을 가져다 쓰는게 빠르긴 했을 것이라고 생각이 든다.
또한, len()함수가 아니더라도 다른 코드부분에서 늦어졌을 것이라고 생각이 든다.

그리고 사실 이 문제는 집합과 맵이라는 알고리즘의 문제이기 때문에 집합을 이용하여 풀어보는것이 이 문제의 풀이 방법 중 하나이기 때문에 집합으로도 풀었다.
확실히 집합을 이용한 실행시간이 더 빠르고, 코드가 더 간단하다.

왜 집합이 더 빠른가 알아보았다.

숫자가 카드 셋에 들어있는지 검사할 때의 시간복잡도는 O(1)이다.
그 이유는 set이 내부적으로 hash를 사용하는 자료구조이기 때문이다.
set에는 값 자체를 바로 저장하는게 아니라, hash function를 거쳐 hash 값으로 변환 후 저장한다. 이 때 원래의 값과 hash는 key-value의 구조를 가지기에, 탐색의 시간복잡도가 O(1)인 것이다.
참고로, 삽입과 삭제도 O(1)이다. 다만, 삽입은 어떤 값을 해시로 변환했을 때 해시테이블에 그 값이 이미 들어있을 수도 있으므로, 충돌 여부 검사를 거쳐 O(N)까지 걸릴 수 있지만, 파이썬에서는 내부적으로 이러한 해시 충돌을 커버해주는 코드가 있으므로 삽입도 O(1)로 수행가능하다고 한다.
참고 사이트