import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(1000000)
def midsort(array,start,end,target):
if start > end:
return 0
mid = (start+end) // 2
if target < array[mid]:
return midsort(array,start,mid-1,target)
elif target > array[mid]:
return midsort(array,mid+1,end,target)
elif target == array[mid]:
return 1
N = int(sys.stdin.readline())
array = list(map(int,sys.stdin.readline().split()))
array.sort()
M = int(sys.stdin.readline())
target = list(map(int,sys.stdin.readline().split()))
for i in range(M):
bool = midsort(array,0,N-1,target[i])
if bool == 1:
print("YES")
else:
print("NO")
재귀함수를 사용하다보니 반드시 start > end라면 return으로 함수를 끝내줘야 한다 .
안그러면 무한한 재귀가 돌아가게 되므로
일단 array.sort()를 해줘야 하는데
저 파이썬 내장함수 sort()가 퀵정렬을 통해 정렬하므로 원소의 개수가 N개라면 O(NlogN)만큼 소요된다
또 이진탐색이 찾아야하는 원소를 절반씩 줄여주므로 O(logN),이것을 M번 수행해야 하므로 총 소요시간은 O(MlogN)
총 소요시간 : O((M+N)logN) 이 소요되었다.
또 문법에서 데이터의 크기가 너무 커지면 input 함수에서 감당할 수 없는 경우가 종종 나오는데,
이를 방지하기 위하여 sys.stdin.readline()을 통해 입력을 받아줘야 한다.
또 잘 까먹는 입력 예시
0 1 2 5 6
이 배열에 순서대로 저장되게 하고 싶다면
array = list(map(int,sys.stdin.readline().split())
split() 자체가 공백을 기점으로 구분이다. 공백 기점으로 배열에 원소 하나씩 저장시킬 것
'알고리즘 문제 풀이' 카테고리의 다른 글
[이코테] 다이나믹 프로그래밍 실전문제 3번 (0) | 2023.06.29 |
---|---|
[이코테] 이진 탐색 실습문제 3번 (0) | 2023.06.28 |
[DFS]백준 24479 파이썬 풀이 (0) | 2023.05.31 |
[DFS] 백준 1707 파이썬 풀이 (0) | 2023.05.28 |
백준 13305 파이썬 풀이 (0) | 2023.05.26 |