[Python] 이것이 코딩테스트다 with 파이썬 - 이진 탐색 - 부품 찾기

들어가기 앞서

 

해당 문제 및 해설은 "이것이 코딩 테스트다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다.

 

이것이 코딩테스트다 with 파이썬 책 구매처

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

 

---

 

이진 탐색 : 반으로 쪼개면서 탐색하기

 

이진 탐색(Binary Search) 는 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 이다.

데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 찾을 수 있다는 특징이 있다.

'이진 탐색' 이름 그대로 탐색 번위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 

 

---

 

부품 찾기 - 문제

 

전자 매장에는 부품이 N 개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

 

N = 5
[ 8, 3, 7, 9, 2 ]

 

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

 

M = 3
[ 5, 7, 9 ]

 

이 때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면, YES 를 없으면 NO 를 출력한다. 구분은 공백으로 한다.

 

입력 조건

 

• 첫째 줄에 정수 N 이 주어진다. ( 1 ≤ N ≤ 1,000,000 )
• 둘째 줄에는 공백으로 구분하여 N 개의 정수가 주어진다. 이 때 정수는 1 보다 크고 1,000,000 이하 이다.
• 셋째 줄에는 정수 M 이 주어진다. ( 1 ≤ M ≤ 1,000,000 )
• 넷째 줄에는 공백으로 구분하여 M 개의 정수가 주어진다. 이 때 정수는 1 보다 크고 10억 이하이다.

 

출력 조건

 

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 YES 를 없으면 NO 를 출력한다.

 

입력 예시	출력 예시
5 8 3 7 9 2 3 5 7 9	NO YES YES

 

코드 (계수 정렬)

 

# N 을 입력 받기
n = int(input())
array = [0] * 1000000

# 가게에 있는 전체 부품 번호를 입력 받아서 기록
for i in input().split():
	array[int(i)] = 1
    
# M 을 입력 받기
m = int(input())

# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인

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

 

코드 II (이진 탐색)

 

# 이진 탐색 소스코드 구현(반복문)

def binary_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


# N (가게 부품 개수) 입력 받기
n = int(input())

# 가게에 있는 전체 부품 번호를 공백으로 구분하여 입력
array = list(map(int, input().split()))

# 이진 탐색을 수행하기 위해 사전에 정렬 수행
array.sort()

# M (손님이 확인 요청한 부품 개수) 입력
m = int(input())

# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x :
	result = binanry_search(array, i, 0, n-1)
    
    if result != None:
    	print('YES', end = ' ')
    else :
    	print('NO', end = ' ')