My code
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
else:
return binary_search(array, target, mid + 1, end)
n = int(input())
array = list(map(int,input().split()))
array.sort()
m = int(input())
needs = list(map(int,input().split()))
for i in needs:
result = binary_search(array, i, 0, n - 1)
if result == None:
print("no", end = ' ')
else:
print("yes", end = ' ')
Answer 1 : 이진 탐색으로 풀이한 방법
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 = int(input())
array = list(map(int,input().split()))
array.sort()
m = int(input())
x = list(map(int,input().split()))
for i in x:
result = binary_search(array, i, 0, n - 1)
if result != None:
print('yes', end = ' ')
else:
print('no', end = ' ')
Answer 2 : 계수 정렬을 이용하여 풀이한 방법
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 = ' ')
Answer 3 : 집합을 이용하여 풀이한 방법
n = int(input())
array = set(map(int,input().split()))
m = int(input())
x = list(map(int,input().split()))
for i in x:
if i in array:
print('yes', end = ' ')
else:
print('no', end = ' ')
Code Review
-My code
이번 문제는 손님이 문의한 부품 M개가 가게 안에 모두 있는지 확인하여 출력하는 문제였습니다. 가게 안의 부품 N 개 중 손님이 문의한 부품이 있는지 확인하기 위해서는 가게 안의 부품을 탐색해야 합니다. 이때 탐색해야 하는 부품의 개수가 많으므로 이진 탐색을 이용하면 쉽게 문제를 해결할 수 있습니다.
따라서 이진 탐색 함수 binary_search 를 재귀함수를 이용하여 구현해주었습니다. 가게 부품 개수와 부품 번호 리스트를 입력 받은 뒤 손님이 요청한 부품 개수와 번호 리스트를 입력 받아 주었습니다. 여기서 주의 할 점은 이진 탐색은 리스트가 정렬 된 상태에서 빠르게 동작합니다. 따라서 탐색할 리스트인 array 를 sort 함수를 이용하여 오름차순으로 정렬해주었습니다. 손님이 요청한 부품 번호를 하나씩 확인해가며 해당 부품이 있는지 확인해주었고 만약 있다면 yes, 없다면 no 를 출력하도록 해주었습니다.
-Answer 1
Answer 1 또한 이진 탐색을 이용하여 구현한 코드 입니다. 이진 탐색 알고리즘을 반복문을 이용하여 구현해주었습니다.
-Answer 2
Answer 2 는 계수 정렬을 이용하여 구현한 코드 입니다. 부품이 있는지 그 여부를 저장할 배열을 새로 하나 만들어 준 뒤, 가게 부품이 입력 되었을 때 배열의 해당 번째에 1을 저장하여 부품이 있다는 것을 표시하도록 해주었습니다. 그런 다음 손님이 요청한 부품 번호를 하나씩 확인해 가며 배열에 1이 저장되어 있다면, 즉 부품이 존재한다면 yes 를 출력하도록, 그렇지 않다면 no 를 출력하도록 해주었습니다.
-Answer 3
Answer 3 는 집합 자료형을 이용하여 구현한 코드 입니다. 가게에 있는 부품 번호를 입력 받아 집합 자료형에 기록해주고 만약 손님이 요청한 부품 번호가 해당 집합 안에 존재한다면 yes, 존재하지 않다면 no 를 출력하도록 해주었습니다.
댓글