[Python][이코테] 부품 찾기

입력 조건

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

 

출력 조건

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

 

입력 예시

5
8 3 7 9 2
3
5 7 9

 

출력 예시

no yes yes

---

앞선 이진탐색 알고리즘을 연습하기위해 재귀와 반복문 두가지 방법을 사용했고

 

추가적으로 만약 이걸 상관없이 풀었을 경우 코드 또한 풀었다.

 

1. 이진탐색 재귀

# 7-3 이진 탐색 부품 찾기
n = int(input())
data1 = list(map(int, input().split()))
data1.sort()
m = int(input())
data2 = list(map(int, input().split()))

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


for i in range(m):
    print(binary_search(data1, data2[i], 0, n-1), end=' ')

 

2. 이진탐색 반복문

# 7-4 이진 탐색 부품 찾기(반복문)
n = int(input())
data1 = list(map(int, input().split()))
data1.sort()
m = int(input())
data2 = list(map(int, input().split()))

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

for i in data2:
    print(binary_search(data1, i, 0, n-1), end=' ')

 

우선 두 코드의 공통점으로는 쉬운 이진탐색을 위해 data1.sort()를 하였다는 것이다. 이 부분만 유의하면 될 것 같다.

 

3. 다른 방법

# 7-5 이진 탐색 부품 찾기(최적화)
n = int(input())
data1 = list(map(int, input().split()))
m = int(input())
data2 = list(map(int, input().split()))

for i in data2:
    if i in data1:
        print("yes", end=' ')
    else:
        print("no", end=' ')

in 을 이용하여 풀었다.