1920번 수 찾기

문제 출처 : https://www.acmicpc.net/problem/1920

---

1920번: 수 찾기

---

처음에 시간초과 난 코드

N=int(input())
n=list(map(int, input().split()))
M=int(input())
m=list(map(int, input().split()))
result=[]
for i in m:
    if i in n:
        result.append(1)
    else:
        result.append(0)
for i in result:
    print(i)

백준은 풀다보면 시간초과 문제에서 많이 실패하는 것 같다,,ㅠㅠㅠㅠㅠ

그래서 생각해보니 위의 내 풀이는 값을 하나하나 다 비교해보기 때문에 시간초과가 났다고 생각을 해 이분탐색으로 바꿔보았다.

두번째 성공한 코드

import sys #입력 시간 줄임

def solve(n,m): #이분탐색에 해당하는 함수
    start=0
    end=len(n)-1
    
    while start<=end:
        mid=(start+end)//2
        if m==n[mid]:
            return 1
        elif m>n[mid]:
            start=mid+1
        elif m<n[mid]:
            end=mid-1
    return 0

N=int(input())
n=list(map(int, sys.stdin.readline().split()))
M=int(input())
m=list(map(int, sys.stdin.readline().split()))

n.sort()

for i in range(M):
    print(solve(n,m[i]))

시간초과를 줄이기 위해 입력도 sys를 import해서 사용하고 이분탐색으로 풀었다..!

시간복잡도 공부를 많이 해야겠다ㅠ_ㅠ