[이진탐색] 이진탐색 (4) 실전 문제 - 부품 찾기

이코테 p.197 실전 문제 - 부품 찾기

입력 예시

5  8 3 7 9 2 3 5 8 9

출력 예시

no yes yes

해당 문제는 총 3가지 방법으로 풀 수 있음

(1) 이진 탐색 이용

내 소스코드

• 이진 탐색을 이용하여 전체 제품 리스트에 고객이 원하는 리스트의 원소가 존재하는지 확인
• 이진 탐색을 사용하기 위해서는 먼저 정렬을 수행해야 함

# 입력 받기
import sys
n = int(sys.stdin.readline().rstrip())
my_list = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(sys.stdin.readline().rstrip())
client_list = list(map(int, sys.stdin.readline().rstrip().split()))

def binary_search(array, target, start, end):
  if start > end:
    return False
  mid = (start + end) // 2
  if array[mid] == target:
    return True
  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  else:
    return binary_search(array, target, mid + 1, end)

my_list = sorted(my_list)
for i in client_list:
  if binary_search(my_list, i, 0, n - 1) == True:
    print('yes', end = ' ')
  else:
    print('no', end = ' ')

교재 소스코드

• 매장 내 N개의 부품을 번호를 기준으로 정렬
• M개의 찾고자 하는 부품이 각각 매장에 존재하는지 검사
• 부품을 찾는 과정에서 최악의 경우 시간 복잡도는 O(M x logN) & N개의 부품을 정렬하는 과정에서 시간 복잡도는 O(N x logN)
  • 결과적으로 시간 복잡도는 O((M + N) x logN)

# 입력 받기
n = int(input())
array = list(map(int, input().split()))
array.sort() # 이진 탐색을 수행하기 위해 사전에 정렬 수행
m = int(input())
x = list(map(int, input().split()))

# 이진 탐색 함수
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

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
  result = binary_search(array, i, 0, n - 1)
  if result != None:
    print('yes', end = ' ')
  else:
    print('no', end = ' ')

(2) 계수 정렬 이용

내 소스코드

• 계수 정렬을 이용하여 제품 리스트에 존재하는 제품들의 개수를 cnt 리스트에 기록함
• 고객이 원하는 리스트의 i번째 원에 대해서, cnt 리스트의 i번째 인덱스의 원소가 0보다 크다면 제품 리스트에 해당 원소가 하나 이상 존재한다는 의

# 입력받기
n = int(input())
array = list(map(int, input().split()))
m = int(input())
client_list = list(map(int, input().split()))

cnt = [0] * (n + 1)
# i번째 부품이 존재하면 해당 인덱스 1씩 증가
for i in range(n):
  cnt[array[i]] += 1

for i in client_list:
  if cnt[i] > 0:
    print('yes', end = ' ')
  else:
    print('no', end = ' ')

교재 소스코드

• 모든 원소의 번호를 포함할 수 있는 크기의 리스트 만들기
• 해당 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인

# N 입력받기
n = int(input())
array = [0] * 1000001

# 가게에 있는 전체 부품 번호를 입력받아서 기록
for i in input().spit():
  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 = ' ')

(3) 집합 자료형 이용

교재 소스코드

• set() 함수는 집합 자료형을 초기화할 때 사용
• 집합 자료형은 단순히 특정 데이터가 존재하는지 검사할 때 매우 효과적
• 3가지 방법 중 간결성 측면에서 가장 우수한 코드

# 입력 받기
n = int(input())
# 가게에 있는 전체 부품 번호를 집합(set) 자료형에 기록
array = set(map(int, input().split()))
m = int(input())
client_list = list(map(int, input().split()))

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

 

3가지 방법 모두 효과적으로 문제 해결 가능