[백준] 1920번 수 찾기 - 파이썬(Python)

문제 (링크)

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

나의 풀이

from sys import stdin

n = stdin.readline()

# 이진탐색을 진행해야하므로 탐색을 할 리스트를 sorted 처리 해준다
group_n = sorted(list(map(int, stdin.readline().split())))

m = stdin.readline()
group_m = list(map(int, stdin.readline().split()))

# 이진탐색을 위한 함수 작성
def binary_search(arr, target, start, end):
	if start > end:
    	return 0 # 값을 못 찾을 땐 0을 리턴
        
    mid = (start + end) // 2
    
    if arr[mid] == target:
    	return 1 # 값을 찾으면 1을 리턴
	
    elif arr[mid] < target:
    	return binary_search(arr, target, mid+1, end)
    
    else:
    	return binary_search(arr, target, start, mid-1)

for i in range(group_m):
	target = group_m[i]
    start = 0
    end = len(group_n)
	print(binary_search(group_n, target, start, end)  

단순히 반복문을 돌며 group_n과 group_m을 비교해줄 경우, 시간초과 판정이 뜨기 때문에 이진탐색을 진행해줘야한다.

 

이진탐색은 위의 코드와 같이 재귀적 방식으로 구현해줄 수 있으며, 아래의 코드처럼 반복문으로도 구현해줄 수 있다.

 

from sys import stdin

n = stdin.readline()

# 이진탐색을 진행해야하므로 탐색을 할 리스트를 sorted 처리 해준다
group_n = sorted(list(map(int, stdin.readline().split())))

m = stdin.readline()
group_m = list(map(int, stdin.readline().split()))

# 이진탐색을 위한 함수 작성
def binary_search(arr, target, start, end):
	while start <= end:
    	mid = (start + end) // 2
        
        if arr[mid] == target:
        	return 1
		
        elif arr[mid] < target:
        	start = mid + 1
		
        else:
        	end = mid - 1

	return 0 # while문을 빠져나오면 찾는 값이 없다는 것이기 때문에 0을 리턴

for i in range(len(group_m)):
	target = group_m[i]
    start = 0
    end = len(group_n)
	print(binary_search(group_n, target, start, end)

 

재귀적 방식을 통해 값을 탐색하게 되면, 반복문을 한 번 돌 때마다 탐색하는 리스트의 절반을 줄여주기 때문에, 결과적으로는 logN 연산만에 모든 값을 돌 수 있게 된다.