[이진 탐색 알고리즘] 문제1 - 부품 찾기(197p)

[이코테] 문제1 - 부품 찾기(197p)

(한줄평) 집합을 이용하여 쉽게 풀 수 있었던 문제! 하지만 다른 풀이 방법으로도 풀어보는 것을 추천!

이 문제는 부품 목록 n개, 손님이 구매를 원하는 부품 m개가 있을 때, 손님이 요쳥한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no를 출력하는 문제다.

이진 탐색, 집합, 계수 정렬 3가지 방법으로 모두 효과적으로 풀 수 있는 문제다. 

(풀이1) 집합(set)을 이용

풀이 시간: 5분 이내

1) 문제 해결 아이디어

단순히 특정 수가 있는지 여부를 검사하면 되기 때문에 부품목록(graph)를 집합으로 선언한다.

 

Q. 리스트가 아닌 집합으로 선언한 이유는?

집합에서 in 연산의 시간복잡도가 O(1)이고 리스트에서 in 연산의 시간복잡도는 O(n)이다.

 

2) 소스코드

# 1. 집합(set) 이용
n = int(input())  # 부품 개수
array = set(map(int, input().split()))  # n개의 부품목록(집합)
m = int(input())  # 구매 원하는 부품 개수
order = list(map(int, input().split()))  # m개의 부품 위시리스트

for i in order:
  # 해당 부품이 부품목록에 있는지 검사
  if i in array:
    print("yes", end=" ")
  else:
    print("no", end=" ")

(풀이2) 이진 탐색

풀이 시간: 10분 이내

1) 문제 해결 아이디어

이진 탐색을 반복문을 이용하여 구현하였다.

이진 탐색을 하기 위해서는 해당 리스트가 오름차순 정렬되어있어야 한다는 것을 기억하자!!

 

2) 소스코드

# 2. 이진 탐색
def binary_search(array, target, start, end):
  while True:
    # 시작점과 끝점이 엇갈렸으면 못찾음
    if start > end:  return "no"
    mid = (start + end) // 2  # 중간점
    
    # 1. 중간값이 타겟이면
    if array[mid] == target:  return "yes"
    # 2. 중간값보다 작으면 왼쪽 탐색
    elif array[mid] > target:  end = mid - 1
    # 3. 중간값보다 크면 오른쪽 탐색
    else:  start = mid + 1
    
n = int(input())  # 부품 개수
array = list(map(int, input().split()))  # n개의 부품목록
m = int(input())  # 구매 원하는 부품 개수
order = list(map(int, input().split()))  # m개의 부품 위시리스트

array.sort()  # 이진 탐색을 위한 오름차순 정렬

# n개의 부품에서 target
for target in order:
  print(binary_search(array, target, 0, n - 1), end=" ")

(풀이3) 계수 정렬

풀이 시간: 5분 이내

1) 문제 해결 아이디어

부품 번호는 1이상 1,000,000이하이기 때문에 모든 부품 번호를 포함할 수 있는 크기 1000001인 리스트를 0으로 초기화하여 생성한다. 구매 원하는 부품 번호에 해당하는 인덱스의 값을 1로 바꾸어 준다.

for문으로 입력받은 구매 원하는 부품(order)에 대해 구매 원하는 부품 번호의 값이 1이라면 부품이 있다는 뜻이다.

 

2) 소스코드

# 3. 계수 정렬
n = int(input())       # 부품 개수
array = [0] * 1000001  # 부품목록 카운팅
for i in map(int, input().split()):
  array[i] = 1  # 체크
m = int(input())  # 구매 원하는 부품 개수
order = list(map(int, input().split()))  # m개의 부품 위시리스트

for i in order:
  # 부품이 있는지 확인
  if array[i] == 1:  print("yes", end=" ")
  else:  print("no", end=" ")