[백준-1920] 수 찾기 파이썬, 파이썬 한줄 입력받기 및 정수형 리스트 변환, 리스트 슬라이스 시간복잡도

# 문제

 

# 실패한풀이

## 선형 탐색

선형탐색 알고리즘으로 찾았을 시에는 시간초과 오류 발생

 

## 이진탐색

[알고리즘] 이진탐색 파이썬 및 시간복잡도

저번에 정리한 내용으로 풀었으나 시간초과 오류 발생, 원인을 분석했을때 재귀함수가 호출할때 리스트를 슬라이싱해주는데 여기서 시간이 초과되는거 같았다. 리스트를 넘겨주지 않고 기존에 데이터를 활용하고 인덱스만 바꿔주는 방법으로 재시도했다.

 

# 성공한 풀이

이진탐색을 똑같이 활용 했으나, 기존 리스트를 그대로 넘겨주는 방법을 사용했다.

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는 슬라이싱 하는 범위의 크기이다.