[정렬/탐색] 백준 1920 수 찾기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1920번: 수 찾기

 

 

 

2. 문제 풀이

 N개의 숫자들 중에 M개의 숫자가 있는지 탐색하는 문제입니다.

 

2022.02.09 - [Algorithm] - [Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

[Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

 단순히 find, count함수나 in 연산자를 이용하면 '시간 초과'가 납니다. 이진탐색을 구현해서 찾아야 합니다. 관련 설명과 코드는 위 링크에서 보실 수 있습니다.

 

 

 

3. 코드

N = int(input())
numlist = list(map(int, input().split()))
M = int(input())
findlist = list(map(int, input().split()))

#이진 탐색(자료, 찾는 값)
def binarySearch(lst, x):
    start = 0
    end = len(lst)-1

    while start <= end:
        mid = (start + end)//2 # 중앙위치
        if x == lst[mid]: # 중앙값이 찾는 값
            return 1 # 찾았음
        elif x > lst[mid]: # 중앙값보다 큰 경우
            start = mid + 1
        else:
            end = mid - 1 # 중앙값보다 작은 경우
    return 0 # 찾지 못한 경우

# 정렬
numlist.sort()
for i in findlist:
    print(binarySearch(numlist, i))

 이진 탐색을 이용해서 M개의 숫자를 탐색합니다. 원래 이진탐색은 찾았을 경우 인덱스를 반환하지만, 이 문제에서는 '1'을 반환합니다. (해당 수가 있으면 1을 출력, 없으면 0을 출력)