이 문제는 구현은 쉽지만 그냥 for문으로 돌리면 시간초과가 난다 ㅠ 그래서 더 빨리 해결할 수 있는 알고리즘을 찾아야 한다. 빨리 해결하는 방법은 그리 어렵지 않다.
일단 sort를 이용해서 두 수열(A,B)을 내림차순으로 정렬시킨다.
이 때 A의 값을 하나씩 늘리면서 점검하고, B도 값을 늘리면서 점검하는데 만약 B의 어떤 값이 A보다 작은게 나오면 어차피 뒤에 있는 것들도 다 작을 것이므로 그냥 뒤에 있는 것들의 개수를 더해주고(len(B)-j) 다시 A로 패스시킨다.
사실상 A -> A'로 넘어갈 때 어차피 A'은 A보다 작으니까 A가 B에서 그냥 stop해줬던 부분(A가 자기보다 작아서 그냥 pass했던)부터 다시 점검해주면 되니까 B의 앞에 것들은(A가 봤을 때 자기보다 컸으므로 A'에게도 큰 것들이 되므로) 필요가 없게 된다.
import sys
input=sys.stdin.readline
t=int(input())
for i in range(t):
sum=0
N,M=map(int, input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
a=0
b=0
n=len(A)
m=len(B)
while a < n and b < m:
if A[a] > B[b]:
sum += m - b
a += 1
else:
b += 1
print(sum)
'Koala - 5기 > 기초 알고리즘 스터디' 카테고리의 다른 글
[백준 / python] 5218번 - 알파벳 거리 (0) | 2022.01.25 |
---|---|
[백준/C++] 14561번 회문 (2) | 2022.01.25 |
[백준/python] 1874: 스택 수열 (0) | 2022.01.25 |
[백준/C++] 1371번 가장 많은 글자 (1) | 2022.01.24 |
[백준/python] - 5363번: 요다 (0) | 2022.01.24 |