부품 찾기

문제

 

 

 

입력

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

 

출력

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

 

입력 예시

5
8 3 7 9 2
3 5 7 9

출력 예시

no yes yes

풀이 방법

어떻게 풀었니

내 코드

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())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))
a.sort()

for i in b:
    result=binary_search(a,i,0,n-1)
    if result == None:
        print("yes", end=" ")
    else:
        print("no", end=" ")

Solution

# N(가게의 부품 개수) 입력
n = int(input())
array = [0] * 1000001

# 가게에 있는 전체 부품 번호를 입력 받아서 기록
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=' ')
//계수정렬

느낀 점

이진 탐색 코드를 정확히 이해하지 못해 코드를 보고 작성을 하였다.

다시 이진 탐색 코드를 재귀적 방법과 반복적 방법에 대해 공부해야겠다.