1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
풀이 참고
https://velog.io/@deannn/BOJ-%EB%B0%B1%EC%A4%80-1920%EB%B2%88-%EC%88%98-%EC%B0%BE%EA%B8%B0-Python
[BOJ] 백준 1920번 수 찾기 (Python)
백준 1920번 수 찾기 [ 실버 4 ] 풀이 python
velog.io
n = int(input())
n_arr = list(map(int,input().split()))
m = int(input())
m_arr = list(map(int,input().split()))
#######################################################
#######################################################
## 작성
# n_arr를 우선 정렬해줘
n_arr.sort()
# m_arr기준으로 이분탐색
for num in m_arr:
lt, rt = 0, n - 1 # 왼쪽 l, 오른쪽 r
cnt = False # cnt로 있는지 없는지 확인 할거야
# 이분탐색 시작
while lt <= rt: # lt가 rt보다 커지면 반복문 탈출
mid = (lt + rt) // 2 # mid는 lt와 rt의 중간값
if num == n_arr[mid]: # num(목표값)이 n_arr[mid]값과 같다면
cnt = True # cnt를 True로 변경
print(1)
break
elif num > n_arr[mid]: # n_arr[mid]가 num보다 작으면
lt = mid + 1 # lt를 높임
else: # n_arr[mid]가 num보다 크다면
rt = mid - 1 # rt를 낮춤
if not cnt: # 찾지 못한 경우
print(0)
댓글