[BOJ] 1920 수 찾기(이분탐색)

ver1) 이분탐색

# 입력
N = int(input())
A = list(map(int, input().split()))
M = int(input())
arr = list(map(int, input().split()))
A.sort()			# A 정렬

# arr의 각 원소별로 이분탐색
for num in arr:
    lt, rt = 0, N - 1		
    isExist = False	

    # 이분탐색 시작
    while lt <= rt:		
        mid = (lt + rt) // 2
        if num == A[mid]:	
            isExist = True	
            print(1)
            break
        elif num > A[mid]:
            lt = mid + 1
        else:			
            rt = mid - 1

    if not isExist:		
        print(0)

1) 일단 리스트 중 한개는 sort 되어 있는게 좋으며

2) 처음과 끝에서 시작할 인덱스값을 이용해 중간값과 비교한다

3) 없으면 A[mid] 값보다 큰 지, 작은 지를 확인한다

4) 크다면 시작점을 하나 더 늘리고

5) 작다면 끝점을 하나 줄여서 다시 반복한다.!!!!

굳이다 이코드 어디서 본건데 어디서 봤는지 기록을 안해놨다.... 죄송,,,,

 

 

 

이분탐색 막연히 어렵다 ~ 하고 넘어갔는데

이중 for문으로 일일이 검사하는 코드로 맞을 수 있는 문제들을 효과적으로 대체할 수 있더랬다 짱이다

 

 

ver2) set

n = int(input())
arr = set(map(int, input().split()))

m = int(input())
find = list(map(int, input().split()))

for num in find:
    print(1) if num in arr else print(0)

 

 

참고

https://somjang.tistory.com/entry/BaekJoon-1920%EB%B2%88-%EC%88%98-%EC%B0%BE%EA%B8%B0-Python

[BaekJoon] 1920번 : 수 찾기 (Python)