# 문제
# 실패한풀이
## 선형 탐색
선형탐색 알고리즘으로 찾았을 시에는 시간초과 오류 발생
## 이진탐색
[알고리즘] 이진탐색 파이썬 및 시간복잡도
# 내용 정렬된 데이터 셋에서 탐색을 시도함 함수가 실행될때마다 탐색하는 범위가 반토막이 되기 때문에 순차탐색에 비해 월등히 속도가 빠름 # 코드 # 이진탐색은 데이터셋이 정렬되어 있어야
devforyou.tistory.com
저번에 정리한 내용으로 풀었으나 시간초과 오류 발생, 원인을 분석했을때 재귀함수가 호출할때 리스트를 슬라이싱해주는데 여기서 시간이 초과되는거 같았다. 리스트를 넘겨주지 않고 기존에 데이터를 활용하고 인덱스만 바꿔주는 방법으로 재시도했다.
# 성공한 풀이
이진탐색을 똑같이 활용 했으나, 기존 리스트를 그대로 넘겨주는 방법을 사용했다.
from sys import stdin, stdout
def answer(data, target,left,right):
mid = (left + right) // 2
if left > right :
return False
if data[mid] == target :
return True
elif target < data[mid] :
return answer(data,target,left,mid-1)
elif target > data[mid] :
return answer(data,target,mid+1,right)
if __name__ == '__main__':
n = stdin.readline()
N = sorted(map(int, stdin.readline().split()))
m = stdin.readline()
M = map(int, stdin.readline().split())
for target in M :
if answer(N, target, 0, len(N)-1) :
print(1)
else:
print(0)
# 그 외
input() 보다는
sys.stdin.readLine()
을 사용하는게 속도가 더 빠르다고 한다.
## 한줄 입력받고 정수형 리스트로 바꾸기
input_list_toint = map(int, stdin.readline().split())
## 리스트 슬라이스의 시간복잡도
list[:n] 와 같이 리스트 슬라이싱을 할 경우 시간 복잡도는 O(k)이다. k는 슬라이싱 하는 범위의 크기이다.
'•알고리즘(Algorithm ) > 문제풀이' 카테고리의 다른 글
[백준-2920] 음계 파이썬, 오름차순 내림차순 판단하기 (0) | 2022.08.03 |
---|---|
[백준-9663] N-Queen 파이썬, 백트랙킹, 파이썬 전역변수, enumerate (0) | 2022.08.03 |
[백준-11399] ATM 파이썬, 탐욕알고리즘을 이용한 최적해 찾기 (0) | 2022.07.28 |
[백준-9461] 파도반 수열 - 동적계획법 이용하기 (0) | 2022.07.23 |
[백준-11726] 2*n 타일링 - 동적계획법 이용하기 (0) | 2022.07.23 |