[백준] 7795번: 먹을 것인가 먹힐 것인가 (Java)

문제: https://www.acmicpc.net/problem/7795

📌 문제 탐색하기

입력 : 첫째 줄 - 테스트케이스
둘째 줄 - A의 수 N과 B의 수 M (1 ≤ N, M ≤ 20,000)
셋째 줄 - A의 크기 배열
넷째 줄 - B의 크기 배열
테스트케이스만큼 둘째 줄 ~ 넷째 줄 반복
출력 : A의 크기가 B보다 큰 쌍의 개수

가능한 시간복잡도

O(N)

알고리즘 선택

투 포인터 알고리즘

📌 코드 설계하기

1. 각 테스트케이스를 반복해 N, M 및 배열 A, B를 input으로 받는다.
2. 배열 A, B를 정렬한다.
3. 배열 B의 현재 비교 위치를 가리키는 포인터인 indexB를 초기화한다.
4. 배열 A의 각 원소에 대해 배열 B의 현재 원소가 A[l]보다 작은 동안 indexB를 증가시킨다.
5. indexB는 A[l]보다 작은 B의 원소 개수를 나타내므로 결과에 더한다.
6. 결과를 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();
            int[] A = new int[N];
            int M = sc.nextInt();
            int[] B = new int[M];
           
            for (int j = 0; j < N; j++) {
                A[j] = sc.nextInt();
            }
            
            for (int k = 0; k < M; k++) {
                B[k] = sc.nextInt();
            }

            Arrays.sort(A);
            Arrays.sort(B);
            
            int result = 0;
            int indexB = 0;
            
            for (int l = 0; l < N; l++) {
                while (indexB < M && B[indexB] < A[l]) {
                    indexB++;
                }
                result += indexB;
            }
            
            System.out.println(result);
        }
        
        sc.close();
    }
}