[이코테] 이진탐색 - 부품 찾기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

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

입력조건

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

출력조건

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

사고과정

• 이진 탐색 소스코드를 활용하자의 관점에서 접근했다. 근데 이진탐색은 정렬된 데이터일 때 사용이 가능하므로 주어진 데이터를 정렬시켜야 했다.(이 때 주어진 데이터를 정렬하는 시간복잡도를 계산했어야 했지만 아직 미숙해서 그냥 넘어갔다.. 해설에서는 Python 정렬 라이브러리가 시간복잡도 $N(logN)$이 걸리므로 괜찮다고 함)
• 주어진 데이터를 정렬시킨 후 탐색하려는 타겟값인 M의 원소들을 하나씩 Loop 돌면서 찾으면 yes, 없으면 no로 출력하도록 짜야지라고 생각함
• 해설을 본 후, 계수 정렬, set(자료형 집합)을 활용한 풀이도 인상적이어서 기록하려고 한다.
• 참고로 계수 정렬은 원소 발생 횟수를 저장해놓을 데이터 범위 크기의 빈 리스트를 정의해야 하고 시작해야 함을 잊지말자!

풀이

1. 나의 풀이(이진탐색 활용)

import sys

# 1. 이진탐색 활용 답안
N = int(input())
N_arr = list(map(int, input().split()))
M = int(input())
M_arr = list(map(int, input().split()))

N_arr = sorted(N_arr)

def binary_search(array, target, start, end):
    while start <= end:
        middle = (start + end) // 2
        if array[middle] == target:
            return 'yes'
        elif array[middle] < target:
            start = middle + 1
        else:
            end = middle - 1
    return 'no'

for m in M_arr:
    res = binary_search(N_arr, m, 0, N-1)
    print(res, end=' ')

2. 계수 정렬 활용

import sys

# 2. 계수정렬 활용 답안 -> 계수정렬은 원소 발생 횟수를 담을 빈 리스트를 정의해야 함
array = [0] * 1000001
N = int(input())
for i in input().split():
    array[int(i)] = 1
M = int(input())
M_arr = list(map(int, input().split()))
for m in M_arr:
    if array[m] == 1:
        print('yes', end=' ')
    else:
        print('no', end=' ')

3. 집합 자료형인 set 활용

import sys

# 3. 집합 자료구조(set) 활용 답안
N = int(input())
N_arr = set(map(int, input().split()))
M = int(input())
M_arr = list(map(int, input().split()))

for m in M_arr:
    if m in N_arr:
        print('yes', end=' ')
    else:
        print('no', end=' ')