[알고리즘]백준_먹을 것인가 먹힐 것인가_7795_python

• 알고리즘 유형 : 정렬, 이분탐색
• 풀이 참고 : 블로그
• 문제 링크 : https://www.acmicpc.net/problem/7795

---

풀이 요약

처음 완전탐색으로 풀었으나 시간초과

이분탐색이나 투포인터로 풀어야 한다고 한다. 

 

이분탐색풀이를 보던 중 재밌는 라이브러리를 찾아 정리

 

[bisect]

첫 번째 인자로는 탐색할 리스트(arr), 두 번째 인자로는 비교값(x)을 넣는다. 

반드시 정렬된 리스트에 사용되어야 하고 arr에 x를 삽입할 곳을 이분탐색으로 찾아 그 인덱스를 반환한다. 

---

코드(python)

import bisect

t = int(input())

for _ in range(t):
    a, b = map(int, input().split())
    arr = []
    for i in range(2):
        sort_arr = sorted(list(map(int, input().split())))
        arr.append(sort_arr)

    count1 = 0
    for i in arr[0]:
        count1 += (bisect.bisect(arr[1], i-1))
    print(count1)

---

배운 점, 배울 점

파이썬은 참 신기한 라이브러리가 많다.