문제
심해에는 두 종류의 생명체 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.
.png)
두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)
출력
각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
T = int(input())
for i in range(T):
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
A.sort()
B.sort()
start = 0
count = 0
for j in range(N):
while True:
if start==M or A[j]<=B[start]:
count+=start
break
else:
start+=1
print(count)
풀이 방식
핵심은 sort를 해서 A와 B를 오름차순으로 만드는 것이다.
한번 오름차순이 되었다면, A의 특정 원소의 차례가 되었을 때, 처음부터 B랑 비교하는게 아니라, 자신보다 이전 index의 원소가 끝난 지점에서부터 시작하면 된다.
왜나면 본인보다 이전 index의 원소보다는 자신이 더 크기 때문이다.
실생활로 예를 들면 자신보다 키가 작은 친구가 어느 특정 집단에서 키가 제일 크다고 해보자.
그럼 본인이 그 집단에 갔을 때 제일 큰 사람이 되는것은 그 사람들과 일일이 비교해보지 않고도 미리 알 수 있는 것과 같다.
자신보다 작은 친구가 그 집단에서 짱을 먹었기 때문이다.
이 포인트를 이용해서 풀면 된다.