[백준/BOJ] 1920번: 수 찾기(파이썬3/Python3)

문제

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

1920번: 수 찾기

---

생각

N개의 정수를 입력받아서 리스트에 저장해둔다.

M개의 수를 입력받아서 리스트에 저장해둔 뒤, 순서대로 for문을 돌려 in인지 not in인지 출력하면 끝!

---

코드

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

for i in X:
  if i in A:
    print(1)
  else:
    print(0)

처음에 쉽다고 생각하고 이렇게 풀었지만 시간초과가 떴다. 

문제를 다시 읽어보니 숫자가 각각 최대 십만까지...

리스트를 다 확인하지 않아도 되는 방법을 생각해야했다. 

 

아무래도 숫자다보니 정렬하면 중간에 빠져나오는 판단을 하기 쉽지 않을까 생각이 들었다. 

그래서 나온 코드는

def search(L, v, start, end):
  if start > end:
    return 0
  mid = (start+end) // 2
  if L[mid] == v:
    return 1
  elif L[mid] > v:
    end = mid-1
  else:
    start = mid+1
  
  return search(L, v, start, end)

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

for i in X:
  print(search(A, i, 0, len(A)-1))

이분탐색에 대해 한 번 찾아보면 도움이 될 것이다!