먹을 것인가 먹힐 것인가

먹을 것인가 먹힐 것인가

문제

---

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)

출력

---

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입력 1

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

예제 출력 1

7
1

문제 해석

• 입력받은 A의 리스트와 B의 리스트를 비교해본다.
• A의 원소 한개와 B의 원소들을 비교해보면서 A원소가 B의 원소보다 크면 count를 +1 해준다.
• 완전탐색을 하지 않고 이분 탐색을 써서 실행 시간을 줄인다.

풀이

• B 원소들을 정렬하기 위해 B_sort 라는 리스트를 만들어서 B를 얕은 복사를 한 후 정렬해준다.
• 만약 A 리스트의 원소 1개가 B의 원소중 가장 큰 수보다 크다면 비교해볼 필요 없이 B의 원소 개수만큼 카운트를 올려준다.
• 그게 아니라면?
  • bisect_left를 이용해 index를 구해준다.
  • 여기서 구한 index는 현재 A의 원소가 몇개의 B의 원소보다 크냐의 갯수가 index 값으로 정해진다.
  • count에 index 값을 더해준다.

import sys
from bisect import bisect_left

T = int(sys.stdin.readline())

for i in range(T):
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))
    sort_B = []
    for k in range(M):
        sort_B.append(B[k])
    sort_B.sort()
    B_max = sort_B[-1]
    count = 0
    for j in A:
        if j > B_max:
            count += M
        else:
            index = bisect_left(sort_B, j)
            count += index
    print(count)

고찰

• 쉬운 이분 탐색 문제였다.