https://www.acmicpc.net/problem/10815
문제 이해
- 상근이가 숫자카드 N개를 가지고 있음
- M개의 정수가 주어졌을때 상근이가 보유한 숫자카드와 동일 수이면 1, 아니면 0을 출력
접근방법
완전탐색일 경우 O(M)*O(N)
M개의 주어진 정수에 대해 각각 N번의 검사 필요 (500,000*500,000)→250,000,000,000 (시간초과 발생 예상)
이분탐색일 경우 O(M)*O(log(N))
시간초과 방지를 위해 이분탐색으로 풀기
코드설계
- M개의 정수를 루프로 순회하며 카드 보유 여부 확인
- 이분탐색을 위해 숫자카드는 오름차순 정렬 →숫자카드의 최솟값이 인덱스 0 최댓값은 인덱스 N-1
- 최소,최대 인덱스가 만날때 까지 숫자카드의 범위를 반씩 줄여나가며 탐색
- 동일한 값이 존재할 경우 1출력, 탐색이 끝날때 까지 찾지 못한 경우 0 출력을 m번 반복
코드구현
"""
5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10 """
N=int(input())
cards= sorted(list(map(int,input().split()))) #정렬
M=int(input())
nums=list(map(int,input().split()))
def isin(num):
lo=0
hi=N-1
mid=lo+hi//2
while lo<=hi:
# print(f'lo:{lo} hi:{hi} mid:{mid}' )
if cards[mid]==num:
return True
elif cards[mid]>num:
hi=mid-1
elif cards[mid]<num:
lo=mid+1
mid=(lo+hi)//2
return False
for num in nums:
if isin(num):
print(1,end=' ')
else:
print(0,end=' ')
다음엔 파이썬 이분탐색 bisect 모듈로 푸는 연습을 해야겠다.
