부품 찾기-[이것이 취업을 위한 코딩 테스트다]

📖문제

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 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를 출력한다.

My answer

import sys
input = sys.stdin.readline

N=int(input())
store=list(map(int,input().split()))
store.sort()
M=int(input())
order=list(map(int,input().split()))

def binary_search(target,start,end):
    
    if(start>end):
        print("no")
        return 0
    mid=(start+end)//2
    
    if(store[mid]==target):
        print("yes")
        return 0
    elif(store[mid]<target):
        return binary_search(target,mid+1,end)
    else:
        return binary_search(target,start,mid-1)

for i in order:
    binary_search(i,0,len(store)-1)

import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
store = sorted(map(int, input().split()))
m = int(input())
order = list(map(int, input().split()))

for x in order:
    idx = bisect_left(store, x)

    if store[idx] == x:
        print('yes', end = ' ')
    else:
        print('no', end = ' ')

Another answer

# 이진 탐색 소스코드 구현 (반복문)
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(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백을 기준으로 구분하여 입력
array = list(map(int, input().split()))
array.sort() # 이진 탐색을 수행하기 위해 사전에 정렬 수행
# M(손님이 확인 요청한 부품 개수) 입력
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=' ')

# 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=' ')

# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 입력 받아서 집합(Set) 자료형에 기록
array = set(map(int, input().split()))

# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 존재하는지 확인
    if i in array:
        print('yes', end=' ')
    else:
        print('no', end=' ')

[풀이]

우선 이 문제는 풀이방법이 매우 다양했다. 

우선 my answer 1은 이진(이분)탐색을 재귀로 구현하여 해결한 문제이다. 단순하게 주문한 리스트를 순회하면서 이진탐색 함수를 실행하면 된다. (이때 꼭 리스트를 정렬한 뒤 수행하는 것을 잊지말자.) my answer 2는 같은 이진탐색을 파이썬의 bisect 라이브러리의 bisect_left를 이용하여 해결한 방법이다.

another answer 1은 이진탐색을 반복문으로 구현한것이고, another answer 2는 계수 정렬로 해결한 방법이다. 해당 부품이 있는지 없는지만 확인하면 되기 때문에 단순하게 전체 부품 번호만큼의 빈 리스트를 생성하고, 해당 부품 번호를 인덱스로 가진 리스트에 1을 채워주면된다. 정렬할 때 쓰는 계수 정렬이지만, 이렇게 있는지 없는지를 확인하기위해 사용할 수도 있다. 마지막 another answer 3는 집합을 이용했다. 집합에서의 in함수는 리스트에서의 in 함수보다 빠르기 때문에 단순히 있는지 없는지를 확인하기 위함이라면 위와 같이 집합을 만들어서 in을 통해 해결해도 된다. 

이렇게 여러가지 방법을 이용하여 해결할 수 있지만, 문제의 시간복잡도나 공간복잡도 조건을 확인하고 해결해야 한다.