Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 1920 수 찾기
백준 1920 수 찾기
문제
첫 번재 줄에 자연수 N이 주어진다.
다음줄에는 N개의 정수 A배열이 주어진다.
그 다음 줄에는 자연수 M과 B배열이 주어지는데 이 수가 A안에 존재하는지 알아내는 프로그램을 작성하시오.
입력
- 첫째 줄: 숫자 갯수 N
- 둘째 줄: 숫자 N개
- 셋째 줄: 숫자 갯수 M
- 넷째 줄: 숫자 M개
출력
- 해당 숫자가 존재할 경우 1
- 존재하지 않을 경우 0 출력
해결 방식
이진 탐색 알고리즘 사용
- A배열을 정렬한다.
- 찾으려는 데이터의 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 탐색한다.
코드
n = int(input())
a = list(map(int,input().split()))
m = int(input())
b = list(map(int,input().split()))
a.sort()
start, end = 0, n-1
for num in b:
start, end = 0, n-1
isExited = False
while start <= end:
mid = (start + end) // 2
if num == a[mid]:
isExited = True
print(1)
break
elif num > a[mid]:
start = mid + 1
else:
end = mid - 1
if isExited == False:
print(0)
