심해에는 두 종류의 생명체 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
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const tc = input.shift();
// 각 테스트 케이스에 대한 입력을 처리하기 위한 반복문
for (let i = 0; i < tc; i++) {
const [sizeA, sizeB] = input.shift().split(' ').map(Number);
const arrA = input.shift().split(' ').map(Number).sort((a, b) => a - b);
const arrB = input.shift().split(' ').map(Number).sort((a, b) => a - b);
let result = 0;
let bIndex = 0;
for (const A of arrA) {
// 배열 A의 현재 원소가 배열 B의 원소보다 크고, bIndex가 배열 B의 길이보다 작은 동안 반복
while (A > arrB[bIndex] && bIndex < sizeB) {
bIndex++; // 배열 A의 현재 원소보다 크거나 같은 원소를 찾을 때까지 bIndex를 증가
}
result += bIndex; // bIndex에는 배열 A의 현재 원소보다 작은 원소의 개수 저장
}
console.log(result);
}
✅ 답안 #2
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const tc = input.shift();
let result = [];
// 이진 탐색
const binarySearch = (start, end, target, arr) => {
if (start > end) return start;
const mid = Math.floor((start + end) / 2);
// 배열 B의 중간 인덱스의 값이 target(배열 A의 원소)보다 작으면
if (arr[mid] < target) {
// 시작 인덱스를 'mid + 1'로 설정 후 재귀
return binarySearch(mid + 1, end, target, arr);
} else { // 그렇지 않으면 마지막 인덱스를 'mid - 1'로 설정 후 재귀
return binarySearch(start, mid - 1, target, arr);
}
};
// 각 테스트 케이스에 대한 입력을 처리하기 위한 반복문
for (let i = 0; i < tc; i++) {
const [sizeA, sizeB] = input.shift().split(' ').map(Number);
const arrA = input.shift().split(' ').map(Number);
const arrB = input.shift().split(' ').map(Number).sort((a, b) => a - b);
const startIdx = 0; // 시작 인덱스 0
const endIdx = sizeB - 1; // 마지막 인덱스는 배열 B의 마지막 인덱스로 설정
let count = 0; // 탐색 후 결과(개수) 저장할 변수
// 이진 탐색에 쓰일 target(배열 A의 현재 원소)을 보내기 위한 반복문
for (const target of arrA) {
count += binarySearch(startIdx, endIdx, target, arrB);
}
result.push(count); // 탐색 결과를 result 배열에 담기
}
console.log(result.join('\n'));