전형적인 이진 탐색 문제라고 한다. 이진 탐색을 직접 구현해 본 뒤에 풀어보니 정말 10분도 안되서 풀 수 있었다.
동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.
예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.
손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.
입력
첫째 줄에 정수 N이 주어진다. (1<=N<=1,000,000)
둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
셋째 줄에는 정수 M이 주어진다. (1<=M<=100,000)
넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
출력
첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.
입력 예시
5
8 3 7 9 2
3
5 7 9
출력 예시
no yes yes
#p197
n = int(input())
list1 = list(map(int, input().split()))
m = int(input())
list2 = list(map(int, input().split()))
list1.sort()
def binary_search(array, start, target, end):
if start > end:
return 'No'
median = (start + end) // 2
if array[median] == target:
return 'Yes'
if array[median] > target:
return binary_search(array, start, target, median - 1)
elif array[median]< target:
return binary_search(array, median + 1, target, end)
for i in list2:
print(binary_search(list1, 0, i, len(list1) - 1), end = ' ')
단순히 가게의 부품 리스트를 오름차순으로 정렬한 뒤 요청한 부품 리스트의 원소 별로 이진탐색을 진행하면 끝이었다.
뭔가 맥빠질 정도로 쉽게 풀려서 기분이 이상했다.
또한 교재에서 계수정렬로도 풀 수 있다고도 해서 계수정렬로 풀어보았다. 입력 개수가 1,000,000 이하이기 때문에 적용할 수 있는 것 같다.
#p197 - 계수정렬
n = int(input())
list1 = list(map(int, input().split()))
m = int(input())
list2 = list(map(int, input().split()))
list3 = [0] * (max(list1) + 1)
for i in list1:
list3[i] = 1
for j in list2:
if list3[j] == 1:
print('Yes', end = ' ')
else:
print('No', end = ' ')
풀긴 풀었는데, 나중에 다시 봐보니 잘못 풀었었다. list3을 max(list1)+1만큼이 아니라 m의 범위를 보고 [0] * 10000001로 지정했었어야 했다... 너무 계수정렬의 개념만 보고 있었던 것 같다. 다음엔 문제 조건 또한 주의하면서 구현해야겠다.