백준 1920 - 수찾기( Python )

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

1920번: 수 찾기

 

가장 기본적인 이진탐색(이분탐색)문제이다.

해당 문제의 경우 100,000밖에 되지않기 때문에 순차탐색으로 풀어도되지만 

이진탐색이 훨씬 효율적이므로 이진탐색으로 풀이한다

 

이진탐색은 기본적으로 정렬이 되어있는 상태여야한다.

재귀함수로 풀이해도되고 반복문으로 풀이해도 무관하다

 

 

#반복문으로 풀이

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 =list(map(int, input().split()))

arr1.sort() #리스트 정렬


def search(array, target, start, end):
	#반복문으로 풀이
    while start <= end: #
        mid = (start + end) // 2 #중간값
        if array[mid] == target: #찾은 경우 중값값 리턴
            return mid
        elif array[mid] > target: #찾는 값이 더 작은 경우
            end = mid - 1 #왼쪽 값을 확인해야하므로 끝값을 조정 
        else: #찾는 값이 더 큰경우
            start = mid + 1 #오른쪽 값을 확인해야하므로 시작값을 조정
    return None


for i in arr2:
    result = search(arr1, i, 0, n - 1)
    if result != None:
        print(1)
    else:
        print(0)

 

간결한 방식으로는 set 자료형을 써서 풀이할 수 있다. 

n = int(input())
array = set(map(int, input().split())) #set 자료형 작성
m = int(input())
array2 = list(map(int, input().split()))

for i in array2:
    if i in array: #찾은 경우 
        print(1)
    else:
        print(0)