[python] 백준 1920 :: 수 찾기 (이분 탐색)
2023. 3. 9. 17:25ㆍAlgorithm
728x90
반응형
[수 찾기]
# 문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
# 입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
# 출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
풀이
n_list = set(map(int, input().split()))
m = input()
m_list = list(map(int, input().split()))
for target in (m_list):
print(1 if target in n_list else 0)
- n_list의 중복을 제거하지 않으면 시간 초과가 발생해서, set으로 변환해서 중복을 제거해야 한다!!
이분 탐색 풀이
이분 탐색
# 입력 받기
n = int(input())
n_list = list(map(int, input().split()))
m = int(input())
m_list = list(map(int, input().split()))
# 이분 탐색 함수 정의
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return 0
# 정렬 후 이분 탐색을 이용하여 m_list의 요소가 n_list에 존재하는지 확인
n_list.sort()
for target in m_list:
print(binary_search(n_list, target))
속도 비교
- 이분 탐색을 사용하지 않은 코드가 더 빠르다..😅
728x90
반응형
'Algorithm' 카테고리의 다른 글
[python] 백준 2805 :: 나무 자르기 (이분 탐색, 시간 초과 해결 방안) (0) | 2023.03.09 |
---|---|
[python] 백준 6603 :: 로또 (백트래킹 풀이, itertools 풀이) (0) | 2023.03.09 |
[python] 백준 2503 :: 숫자 야구 (백트래킹 풀이, itertools 풀이) (0) | 2023.03.09 |