부품 찾기

출처:: 

분류:: 이진탐색

 

1. 문제 이해 및 해결과정

  1)이진탐색 풀이

 - N개의 부품 M개의찾고자하는 부품 O(MlogN) -> 200만번의 연산 

 - N개의 부품 정렬 O(NlogN)

 => 시간복잡도 : O((M+N)logN) 

 

2. 풀이방법

 1. 이진탐색

#부품 찾기
#
import sys
sys.stdin = open("input.txt","r")
n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))
a.sort() #이진탐색 수행하기 위해
def binary_search(arr,d):
    s=0
    e=len(a)-1
    while s<=e:
        m=(s+e)//2
        if a[m]==d:
            return True
        elif a[m]>d:
            e= m - 1
        elif a[m]<d:
            s = m + 1
    return False

for x in b:
    res=binary_search(a,x)
    if res==True:
        print("yes")
    else:
        print("no")

  2. 계수 정렬

#부품 정렬
#
import sys
sys.stdin = open("input.txt","r")
n=int(input())
arr=[0]*1000000

for i in input().split():
    arr[int(i)]=1

m=int(input())
b=list(map(int,input().split()))

for x in b:
    if arr[x]==1:
        print('yes',end=' ')
    else:
        print('no',end=' ')

  3. set() 이용

 

#부품 정렬
#
import sys
sys.stdin = open("input.txt","r")
n=int(input())
a=set(map(int,input().split())) #특정한 수가 한 번이라도 등장했는지 검사하면 되므로 
m=int(input())
b=list(map(int,input().split()))

for x in b:
    if x in a:
        print('yes',end=' ')
    else:
        print('no',end=' ')

3. 오답원인

 

4. 알게된 점