문제

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

예제 입력

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

예제 출력

7
1

내가 했던 풀이 방법

1. count를 0으로 초기화하고, index를 1 증가시킨다. (index는 초기값 0이며, 1을 증가시키는 이유는 테스트 케이스 첫째 줄에는 N과 M이 입력된다. N과 M은 굳이 필요없는 변수이기 때문에 무시해준다.)
2. index를 이용해서 A와 B를 각각 저장해준 뒤, 오름차순으로 정렬해준다.
3. current를 0으로 두고, B를 순환한다. 이때, current는 A의 현재 index이다. 만약, A[current]가 현재 B값보다 큰 경우 count에 A의 크기에서 current를 빼준 값을 더해준다. B값과 같거나 작은 경우 current를 1증가시키고, B의 현재 index를 1 감소시켜준다. (A 크기에서 current를 빼주는 이유는 A와 B를 모두 정렬해주었기 때문에 뒤에 나오는 요소들은 현재 index에서 먹을 수 있는 경우라면 항상 먹을 수 있는 경우이기 때문이다. 그러므로, current를 포함한 뒷 요소의 개수를 전부 count해주면 A를 순회하여 이중 for문을 돌 필요가 없어진다.) (같거나 작은 경우 B의 현재 index를 감소시켜주는 이유는 다음에 나올 A 요소가 현재 B값을 먹을 수 있을지 없을지를 검사하지 않았기 때문에 재검사를 위해 j를 1 감소시켜주어야 한다.)
4. count를 출력하고, 지금까지 과정을 테스트 케이스만큼 반복해준다.

코드

const fs = require('fs');
let [cases, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let index = 0;
let A = [];
let B = [];
let count = 0;
for (let i = 0; i < Number(cases); i++) {
  count = 0;
  index++;
  A = input[index++].trim().split(' ').map(Number);
  B = input[index++].trim().split(' ').map(Number);
  A.sort((a, b) => a - b);
  B.sort((a, b) => a - b);

  let current = 0;
  for (let j = 0; j < B.length; j++) {
    if (A[current] > B[j]) {
      count += A.length - current;
    }
    if (A[current] <= B[j]) {
      current++;
      j--;
    }
  }

  console.log(count);
}

회고

투포인터로 풀이하려다가 이 방법밖에 안 떠올라서 풀어보니 정답이었다. 처음에는 이중 for문으로 A를 돌고, B를 돌면 되긴하겠지라고 생각했는데 시간초과가 분명히 걸릴 것 같았다. 그래도 마땅히 생각나는 게 없어서 이중 for문으로도 풀어보려고 했는데 도중에 위와 같은 방법이 떠올랐던 것이다. '어차피 정렬하면 뒤에 있는 요소들도 다 먹을 수 있잖아?' 오랜만에 풀이 중에 좋은 방법이 떠올랐다. 굿.