[07-05 이진탐색] 부품 찾기

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 에 있는 문제이다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

문제는 책 안에 있다!!

나는 이 문제에 접근하기 위해 아래와 같은 방법을 이용했다.

이는 책에서 제시한 방법과 같았다.

정렬이 되어 있기 떄문에 이진 탐색이 가능한 것이다.

import sys
n = int(sys.stdin.readline().rstrip())
things = list(map(int,sys.stdin.readline().rstrip().split()))
things.sort()

m = int(sys.stdin.readline().rstrip())
find_things = list(map(int,sys.stdin.readline().rstrip().split()))


def binary_search(arr, start, end, target):
    while start<=end :
        mid = (start+end)//2
        if arr[mid] == target:
            return True
        elif arr[mid]  < target :
            start = mid + 1
        else :
            end = mid-1

    return False


for i in find_things :
    if binary_search(things,0,n-1,i) :
        print("yes", end = " ")
    else :
        print("no", end = " ")

 

 

책에서는 계수 정렬로 찾는 방법도 알려주었기 때문에 따라해보았다.

이는 모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 인덱스에 직접 접근하면 된다.

n = int(input())
array = [0] * 1000001

for i in input().split() :
	array[int(i)] = 1

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


for i in x :
    if array[i] == 1 :
        print('yes', end = ' ')
    else:
    	print('no', end = ' ')

 

 

책에서는 집합 자료형을 이용한 방법도 제시하였다. 집합 자료형은 단순히 특정 데이터가 존재하는지 확인할 때 유용하다.

n = int(input())
array = set(map(int,input().split()))

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

for i in x:
    if x in array:
    	print('yes', end = ' ')
    else:
    	print('no', end = ' ')

 

이진 탐색 단원이어서 이진 탐색으로만 접근할 생각을 하였는데, 집합 자료형을 이용하면 훨씬 더 간결하고 직관적으로 작성할 수 있다는 것에 대해 알 수 있었다.