백준 1920

n개의 정수, m개의 정수가 주어질 때,
m개의 정수 각각이 n개의 정수에 포함되어 있는지 출력(0 또는 1)하는 문제이다.

단순하게 생각하면..
m개의 정수가 n개의 정수가 포함된 리스트에 존재하는지 확인하면 되고,
코드는 다음과 같다.

# 1920

import sys

n = int(sys.stdin.readline())
array_n = list(sys.stdin.readline().split())
m = int(sys.stdin.readline())
array_m = list(sys.stdin.readline().split())

# print(n, array_n)
# print(m, array_m)

for i in range(m):
    if array_m[i] in array_n:
        print(1)
    else:
        print(0)

이렇게 하면 시간 초과가 뜬다..!

직후 생각한 풀이는 이진 탐색(binary search)이다.

이진 탐색을 위한 함수를 따로 정의했고,
이진 탐색을 위해 n개의 정수가 담긴 리스트를 오름차순으로 정렬했다.

코드(정답)는 다음과 같다.

# 1920

import sys

def binary_search(start, end, target, array):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return True
        elif array[mid] > target:
            end = mid - 1
        elif array[mid] < target:
            start = mid + 1
    
    return False


n = int(sys.stdin.readline())
array_n = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
array_m = list(map(int, sys.stdin.readline().split()))

# print(n, array_n)
# print(m, array_m)

# 이진 탐색을 위한 리스트 정렬
array_n.sort()

for num_m in array_m:
    if binary_search(0, n - 1, num_m, array_n):
        print(1)
    else:
        print(0)

다른 풀이를 찾아보다 이진 탐색 없이도..
자료형 변환을 통해 문제를 풀 수 있음을 알게 되었다.

List 자료형의 탐색 시간 복잡도는 O(n),
Set 자료형의 탐색 시간 복잡도는 O(1)임을 이용한 것인데,

Set은 해시 테이블로 구현되어 있기 때문에 이러한 차이가 존재한다.

이를 이용한 코드는 다음과 같다.

# Set을 이용한 풀이
import sys

n = int(sys.stdin.readline())
array_n = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
array_m = list(map(int, sys.stdin.readline().split()))

set_n = set(array_n)
for num_m in array_m:
    if num_m in set_n:
        print(1)
    else:
        print(0)

참고

https://yoongrammer.tistory.com/75
https://shinho0902.tistory.com/52