10815번: 숫자 카드
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
<내 코드>
N = int(input())
cards = list(map(int, input().split()))
M = int(input())
nums = list(map(int, input().split()))
cards.sort()
for i in range(M):
low, high = 0, N-1
while low <= high:
mid = (low + high) // 2
if cards[mid] == nums[i]:
print(1, end=" ")
break
elif cards[mid] < nums[i]:
low = mid + 1
else:
high = mid - 1
if low > high:
print(0, end=" ")
break처음에 데이터 양을 생각하지 못하고 브루트포스처럼 풀었었다..
정렬된 리스트를 이분탐색으로 범위를 줄여나가면 많은 데이터에서 빠른 시간에 탐색이 가능하다.
반응형
'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글
| [백준 1026] 보물 - Python (정렬) (0) | 2020.10.16 |
|---|---|
| [백준 1764] 듣보잡 - Python (정렬, 집합) (0) | 2020.10.16 |
| [백준 1449] 수리공 항승 - Python(그리디, 정렬) (0) | 2020.10.08 |
| [백준 2644] 촌수계산 - Python(그래프 탐색, BFS) (0) | 2020.10.08 |
| [백준 2263] 트리의 순회 - Python (트리, 재귀) (1) | 2020.10.07 |