문제
동빈이네 전자 매장에는 부품이 N개 있다. 어느 날 손님이 M개 종류의 부품을 구매하기 위한 견적서를 요청하였다. 손님이 요구한 부품이 매장에 전부 있는지 확인하는 프로그램을 작성해보자.
입력 조건
1. 첫째 줄에 정수 n이 주어진다.
2. 둘째 줄에는 공백으로 구분하여 n개의 정수가 주어진다. (매장 내의 부품코드)
3. 셋째 줄에는 정수 m이 주어진다.
4. 넷째 줄에는 공백으로 구분하여 m개의 정수가 주어진다. (손님이 요구한 부품코드)
출력 조건
1. 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 Yes를, 없으면 No를 출력한다.
내 코드
n = int(input())
a = list(map(int,input().split()))
m = int(input())
b = list(map(int,input().split()))
result = []
for i in range(len(b)):
cnt=0
for j in range(len(a)):
if b[i] == a[j]:
result.append("Yes")
else:
cnt+=1
if cnt == len(a):
result.append("No")
print(result)해설 순차탐색 알고리즘을 이용하였고, 탐색하며 자신과 일치하지 않을 때마다 Count 변수를 1씩 증가해주었습니다. 이 변수가 매장 부품의 총 개수가 되면 일치하는 부품이 없다는 말이므로 result 리스트에 No라는 대답을 입력하게 하였습니다.
교재 코드
a.sort()
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
for i in b:
result = binary_search(a,i,0,n-1)
if result != None:
print('yes',end='')
else:
print('No',end='')교재해설 교재에서는 이진탐색을 사용한 답안을 가장 먼저 보여주고 있습니다. 이진탐색을 위해 리스트를 Sorting해주었고, 일반적인 이진탐색 코드에 반복문을 이용하였네요. b 리스트의 원소가 target이 되어 a 리스트를 탐색하고, 유효한 값을 반환하였다면 (=일치한다면) Yes를 출력하는 방식입니다.
평가 순차탐색보다, 교재에서 사용한 이진탐색이 시간복잡도 면에서 우수합니다. 저는 문제 안에 탐색 코드를 녹이려고 했다면, 교재에서는 formal한 코드를 활용한다는 느낌이네요. 후자가 더 깔끔한 듯 합니다...ㅎㅎ
본 문제는 이진탐색, 순차탐색 이외에도 계수 정렬 혹은 파이썬 내의 집합 자료형을 이용하여 해결할 수 있습니다. 접근 방식은 많지만, 그 중에 가장 빠른 길을 찾는 게 관건인거죠. 그러기 위해선 알고 있는 알고리즘이 많을수록 유리하겠다는 생각을 합니다.
참고
이것이 코딩테스트다 with Python (나동빈 저)
