[백준/python] 1920번 수 찾기

알 수 없는 사용자 2023. 8. 6. 21:33

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

N개의 정수가 있는 집합 A, M개의 정수가 있는 집합 B 존재

-> B의 요소들이 A에 포함되는지 확인

<코드>

<풀이> - 이분탐색

1. 집합 N 정렬

2. 시작과 끝 지점의 인덱스 지정

3. 시작 + 끝 // 2 구하기

4. 중간 지점의 값과 해당 값 비교

-> 동일하면 찾은 것 / 값이 크면 윗부분 탐색 / 값이 작으면 아랫부분 탐색 => 반복

5. 만일, 확인불가하면 없는 것으로 판단