[백준] 7795 먹을 것인가 먹힐 것인가

🌭 문제 설명

• 심해에는 두 종류의 생명체 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보다 큰 쌍의 개수를 출력한다.

---

😎 나의 풀이

T = int(input())

for _ in range(T):
  N, M = list(map(int, input().split()))
  A = list(map(int, input().split()))
  B = list(map(int, input().split()))
  
  A = sorted(A)
  B = sorted(B)
  
  main = 0
  sub = 0
  count = 0
  
  while main < N:
    if sub == M:
      count += sub
      main += 1
    else:
      if A[main] > B[sub]:
        sub += 1
      else:
        count += sub
        main += 1
  print(count)

1. 투 포인터 알고리즘을 이용해서 풀었고 , 테스트 케이스 T 만큼 반복 해준다.
2. 입력받은 A 배열과 B 배열을 각각 오름차순 정렬해준다.
3. 두 개의 배열을 순회한다. A 배열을 순회할 main 과 B 배열을 순회할 sub 그리고 개수를 출력할 count 변수를 초기화 한다.
4. sub가 M과 같으면 sub를 count에 더해주고 main을 한칸 옮겨준다.
5. main이 sub보다 크면 sub를 한칸 옮겨주고 작으면 sub의 값을 count에 더해주고 main을 한칸 이동시켜주면 된다.
6. count 출력

---

🧵 다른 풀이

import sys 
input = sys.stdin.readline

def sol():
    for _ in range(int(input())):
        _,M = map(int,input().split())
        A,B = sorted(list(map(int,input().split()))),sorted(list(map(int,input().split())))
        num = n = 0
        for a in A:
            while n < M and a > B[n]:
                n += 1
            num += n
        print(num)

sol()

1. 이 풀이도 투 포인터이다. 각 배열들을 정렬시켜준다.
2. num에 A[i] > B[j]를 만족하는 쌍의 개수를 저장한다.
3. B 에서 a 보다 작은 원소 B[n]이 있으면 n을 증가한다.
4. num에 n을 누적시킨다.

---

• 다른 풀이는 백퍼센트 이해가 안가기는 하지만 역시 고수들이 많은 듯😇