리스트 입력 여러개 받기과 이진탐색

 

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

1920번: 수 찾기

 

N = int(input())
A = list(map(int, input().split()))
M = int(input())
X = list(map(int, input().split()))

 

이렇게만 평소에 입력 받아서 몰랐는데,

list = []
list.extend(map(int,input().split()))

 

과 같이 같은경우, extend를 이용해서 여러개를 받을수도 있었다.

 

이 문제는 이진 탐색문제인데, 실제 시간복잡도를 고려하지 않고 구현한다면

# 입력 처리
N = int(input())
A = list(map(int, input().split()))
M = int(input())
X = list(map(int, input().split()))

# 각 숫자에 대해 배열 A 안에 존재하는지 확인
for x in X:
    print(1 if x in A else 0)

 

짠 이렇게 심플하게 작성할수 있겠다. 물론 터진다.

 

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return 1
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return 0

# 입력 처리
N = int(input())
A = list(map(int, input().split()))
M = int(input())
X = list(map(int, input().split()))

# 배열 A 정렬
A.sort()

# 각 숫자에 대해 이진 검색 수행
for x in X:
    print(binary_search(A, x))

 

이진탐색을 이용

 

import bisect

# 입력 처리
N = int(input())
A = sorted(map(int, input().split()))  # 정렬된 상태로 입력 받기
M = int(input())
X = map(int, input().split())

# 각 숫자에 대해 이진 검색 수행
for x in X:
    # bisect_left는 x가 삽입될 가장 왼쪽 위치를 반환
    # bisect_right는 x가 삽입될 가장 오른쪽 위치를 반환
    left = bisect.bisect_left(A, x)
    right = bisect.bisect_right(A, x)
    
    # 만약 left와 right가 같다면, x는 리스트에 존재하지 않는 것
    # 존재한다면, left와 right는 다른 값을 가질 것임
    print(1 if left != right else 0)

 

파이썬 내장함수 이용까지 짚고 넘어가자