📚 오늘의 문제
링크 : https://www.acmicpc.net/problem/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보다 큰 쌍의 개수를 출력한다.
예제 입력 1
2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215
예제 출력 1
7
1
문제 풀이
A = [8, 2, 4, 9, 11]
B = [3, 6, 1, 10, 13]
위 테스트 케이스를 생각해보자. A, B를 둘다 오름차순으로 정렬 했을 때
A = [2, 4, 8, 9 ,11]
B = [1, 3, 6, 10, 13]
이와 같은 배열이 될 것이다.
A의 마지막 원소부터 첫 원소까지 (큰 값에서 작은 값 방향으로) 반복을 하고 B배열의 인덱스를 투포인터처럼 움직여 answer을 갱신하는 방식으로 접근했다.
A -> 11
B = [1, 3, 6, 10 ,13]
currentIndex = 4
11보다 작은값을 발견할 때 까지 currentIndex를 감소시킨다.
A -> 11
B = [1, 3, 6, 10 ,13]
currentIndex = 3
즉 A의 11이라는 원소는 0~3까지의 B의 원소를 먹을 수 있으므로 answer에 4의 값을 더해준다.
값을 더한 후 다음 반복문 실행
A -> 9
B = [1, 3, 6, 10 ,13]
currentIndex = 2
9보다 작은 값을 찾을 때까지 currentIndex를 감소시킨 후
원소 9는 0~2까지의 B원소를 먹을 수 있으므로 answer에 3의 값을 더해준다.
위와 같은 로직을 A의 첫번 째 원소까지 반복하여 answer을 갱신하면 A가 B보다 큰 쌍의 개수를 구할 수 있다.
package week10;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj7795 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int t = 0; t<T; t++){ //테스트 케이스 개수
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int answer = 0;
int[] arrN = new int[N];
int[] arrM = new int[M];
st = new StringTokenizer(br.readLine());
for(int i = 0; i<N; i++){//A의 배열 초기화
arrN[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i<M; i++){// B의 배열 초기화
arrM[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arrN); //배열 A 오름차순 정렬
Arrays.sort(arrM); //배열 B 오름차순 정렬
int MIndex = arrM.length-1; //배열 B의 currentIndex
for(int i = arrN.length-1; i>=0; i--){ //A의 원소별 먹을 수 있는 B 원소의 개수 구하기.
while(MIndex!=-1&&arrN[i]<=arrM[MIndex]){ // A 원소보다 작은 B 원소가 나올 때 까지 currentIndex 감소
MIndex--;
}
answer += MIndex+1; //0 ~ currentIndex, 즉 A 원소가 먹을 수 있는 B 원소의 개수 더해주기.
}
System.out.println(answer);
}
br.close();
}
}'알고리즘' 카테고리의 다른 글
| [JAVA] 백준 1520번 "내리막 길" (0) | 2025.05.10 |
|---|---|
| [JAVA] 백준1509번 "팰린드롬 분할" (0) | 2025.05.09 |
| [JAVA] 0x09 백준 9466번 "텀 프로젝트" (0) | 2024.07.02 |
| [JAVA] 0x08 백준 2504번 "괄호의 값" (1) | 2024.06.26 |
| [JAVA] 0x07 백준 11003번 "최솟값 찾기" (2) | 2024.06.19 |