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

❓문제

💭 아이디어

문제를 보자마자 생각한 풀이법은 전체 리스트를 정렬해 이진탐색의 조건을 갖추도록 한 뒤, 찾아야 되는 부품에 대해 반복문을 돌며 하나씩 이진탐색을 통해 찾는 것이었다.

이진탐색을 구현하는 데에도 1. 재귀를 통한 구현 2. 반복문을 통한 구현 두가지가 있다.

나는 재귀를 통해 구현하였다.

추가로 이 문제는 계수 정렬 개념으로도 풀 수 있다.
모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 직접 접근하여 특정 번호의 부품이 매장에 있는지 확인한다. (문제의 입력조건에 N의 범위가 주어지므로 이에 맞게 리스트를 만들면 된다.)

또한 집합 자료형을 이용해 풀 수 있다.
단순히 특정한 데이터가 존재하는지 검사가 필요한 것이므로 집합 자료형을 이용할 수 있다.

❗ 풀이

1. 이진 탐색 - 재귀 & 반복문

n = int(input())
all = list(map(int, input().split()))
m = int(input())
find = list(map(int, input().split()))

all.sort() # 이진 탐색을 위해 정렬
print(all)

# 재귀함수
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)
    
# 반복문
def binary_search2(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 range(m):
    result = binary_search2(all, find[i], 0, n - 1)
    if result == None:
        print("no", end = " ")
    else:
        print("yes", end = " ")

2. 계수 정렬

n = int(input())
array = [0] * 100

# 가게에 있는 전체 부품 번호를 입력 받아 1로 기록
for i in input().split():
    array[int(i)] = 1

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. 집합 자료형

n = int(input())
array = set(map(int, input().split()))

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

for i in x:
    if i in array:
        print('yes', end = ' ')
    else:
        print('no', end = ' ')

✅ Comment

파이썬에서 값이 존재하지 않는 변수에 None을 대입하면 이 변수에 아무런 값이 없다는 것을 나타낼 수 있다.
이진 탐색의 조건은 데이터가 정렬되어 있음 이므로 이 조건을 갖추기 위해 먼저 정렬을 해주어야 한다!

이진 탐색 외에도 계수 정렬과 집합자료형을 통해 풀 수 있음을 기억하자.