[Python] 7795. 먹을 것인가 먹힐 것인가

https://www.acmicpc.net/problem/7795

7795번: 먹을 것인가 먹힐 것인가

 

접근법

• 이분 탐색을 통해 A의 원소가 B의 원소보다 큰 값의 경우의 수를 찾음.
• 이분 탐색을 통해 timeout이 나지 않도록 함.

def input_func():
    a_num, b_num = map(int, input().split())
    a_arr = list(map(int, input().split()))
    b_arr = list(map(int, input().split()))
    a_arr.sort()
    b_arr.sort()
    return a_arr, b_arr

def solution2(a_arr, b_arr):
    count = 0
    for a in a_arr:
        tmp_count = 0
        start, end = 0, len(b_arr) - 1
        while start <= end:
            mid = (start + end) // 2
            if b_arr[mid] < a:
                tmp_count = mid + 1
                start = mid + 1
            else:
                end = mid - 1
        count += tmp_count
    print(count)

def main():
    T = int(input())
    for i in range(T):
        a_arr, b_arr = input_func()
        solution2(a_arr, b_arr)

if __name__ == '__main__':
    main()

---

유의할 점 및 새로 배운 사항

1. bisect 라이브러리

bisect 라이브러리를 활용하면 이분 탐색을 쉽게 풀 수 있다.

 

---

처음 생각했던 알고리즘의 문제점(틀린이유)

try1

(1) 모든 원소를 탐색하니 timeout이 걸림 -> 이분 탐색 활용

def input_func():
    a_num, b_num = map(int, input().split())
    a_arr = list(map(int, input().split()))
    b_arr = list(map(int, input().split()))
    a_arr.sort()
    b_arr.sort()
    return a_arr, b_arr

def solution(a_arr, b_arr):
    count = 0
    for i in a_arr:
        for j in b_arr:
            if i > j:
                count += 1
            else:
                break
    print(count)

def main():
    T = int(input())
    for i in range(T):
        a_arr, b_arr = input_func()
        solution(a_arr, b_arr)

if __name__ == '__main__':
    main()

사용된 알고리즘

정렬, 이분 탐색, 두 포인터