[백준 1920] 수 찾기 - 파이썬

백준 1920 - 수 찾기

 

* 풀이과정

전형적인 이진 탐색 문제이다.

1) 리스트 A를 오름차순 정렬

2) 재귀함수를 활용하여 이진 탐색

• start = 0, end = N-1에서 탐색 시작 (m = (start + end) // 2)
• 리스트 A 의 중앙값 A[m]과 target을 비교하여, 같은 경우 1 출력
• A[m] > target 인 경우, 중앙값 기준으로 왼쪽(-1)까지 다시 탐색 → end = mid -1
• A[m] < target 인 경우, 중앙값 기준으로 오른쪽(+1)부터 다시 탐색 → start = mid + 1
• 재귀함수의 가장 첫번째 조건으로 start > end일 때 0 출력

이진 탐색은 개념만 알고 있었다가 문제는 처음 풀어봤는데, 굳이 재귀를 돌릴 때마다 A 리스트를 slice 해서 넘기는 과정을 넣어서 시간 초과가 나왔다.

사실은 start, end 인덱스만 조정하면 되는 간단한 문제..!

 

N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))

# A 리스트 오름차순 정렬
A.sort()

# 이진 탐색을 위한 재귀함수 생성
def binarySearch(target, start, end):
     mid = (start+end)//2
     if start>end: print(0)		# 탐색을 모두 마쳤는데 동일한 값이 없는 경우 0출력
     # target이 A[mid]보다 작다면 end = mid-1 으로 하여 다시 탐색
     elif target < A[mid]: binarySearch(target, start, mid-1)
     # target이 A[mid]보다 크다면 start = mid+1 으로 하여 다시 탐색
     elif target > A[mid]: binarySearch(target, mid+1, end)
     else: print(1)		# target == A[mid]인 경우 1 출력

for num in B:
     binarySearch(num, 0, N-1)


"""
이건 내가 굳이 리스트를 slice 해서 보내는 작업을 해서, 시간초과가 나온 함수...
def is_Exist(target, lists):
        L = len(lists)
        if L == 1 and target != lists[0]: print(0)
        elif num < lists[L//2]:
            is_Exist(target, lists[0:(L//2)])
        elif target > lists[L//2]:
            is_Exist(target, lists[L//2:L])
        else: print(1)
  """