스터디 문제 풀기

➡️ 수 찾기

import sys

n=int(input())
nlist=set(map(int,sys.stdin.readline().split()))
m=int(input())
mlist=list(map(int,sys.stdin.readline().split()))

# for mm in mlist:
#     if mm in nlist:
#         print(1)  
#     else:
#         print(0)
for mm in mlist:
    print(1) if mm in nlist else print(0)

주석처리한 것 보다 아래가 더 빠르고
sys.stdin.readline()이 input()보다 메모리도 적게 들고 속도도 더 빠르다

처음엔 교집합으로 체크하려고 했는데 if문에서 교집합이나 set을 쓰면 시간초과가 나고 교집합을 따로 해서 if문에 사용해도 되지만 오히려 더 느리다

그리고 같은 수가 있는지 확인만 하면 되는거라서 굳이 int로 바꿔줄 필요가 없었다.. 호달달..

프린트문도 stdout.write로 바꾸면 120ms까지 빨라진다
stdout.write('1\n') if mm in nlist else stdout.write('0\n')

➡️ 수 찾기 다른 풀이

이분탐색으로 푸는 거라구 한다
이분탐색은 시작과 끝 값을 이용해서 범위를 단축시키는 것이기 때문에 리스트를 먼저 정렬시켜줘야한다

import sys

n=int(input())
nlist=sorted(map(int,sys.stdin.readline().split()))
m=int(input())
mlist=list(map(int,sys.stdin.readline().split()))

for mm in mlist:
    start=0
    end=n-1
    while start<=end:
        if mm==nlist[(start+end)//2]:
            print(1)
            break
        elif mm < nlist[(start+end)//2]:
            end=(start+end)//2-1
        elif mm > nlist[(start+end)//2]:
            start=(start+end)//2+1
    if start>end:
        print(0)

그리고 mlist의 요소mm들에 대해서 조건을 만족시키는 동안 start와 end값을 바꿔가면서 탐색범위를 축소시켜나가면서 mm과 일치하는 값이 있는지 확인한다
시간은 훨씬 오래걸리는데 메모리는 47276KB로 더 적게 소요된다

함수로 바꿔볼 수 있는데 그냥 위의 while문을 그대로 쓰는 게 재귀문으로 바꾼 것보다 훨씬 빠르다

# 47268KB	448ms
import sys

def solution(target,start,end):
    while start<=end:
        mid=(start+end)//2
        if target==nlist[mid]:
            return 1
        elif target < nlist[mid]:
            end=mid-1
        elif target > nlist[mid]:
            start=mid+1
    if start>end:
        return 0
    
n=int(input())
nlist=sorted(map(int,sys.stdin.readline().split()))
m=int(input())
mlist=list(map(int,sys.stdin.readline().split()))

for mm in mlist:
    start=0
    end=n-1
    print(solution(mm,start,end))

# 47276KB	520ms
def solution(target,start,end):
    if start>end:
        return 0
    mid=(start+end)//2
    if target==nlist[mid]:
        return 1
    elif target < nlist[mid]:
        end=mid-1
    elif target > nlist[mid]:
        start=mid+1
    return solution(target,start,end)