[백준] 7795번 - 먹을 것인가 먹힐 것인가 [Java][C++]

문제 링크

---

1. 문제 풀이

$A$ 의 각 원소에 대해 $B$ 에서 해당 원소보다 작은 원소의 수를 구해서 전부 합한 결과를 출력하는 문제다. 이분 탐색 또는 투 포인터를 활용하면 간단하게 해결할 수 있다.

1. 이분 탐색

이분 탐색을 활용할 경우 $A$ 의 각 원소에 대해 $B$ 에서 해당 원소 미만인 원소를 찾아야 한다. 이를 위해 $B$ 를 정렬 후 해당 원소 이상인 원소의 최소 인덱스를 반환하는 Lower Bound를 활용했고, 미만인 원소는 이분 탐색의 반환 인덱스 $-1$ 을 해야하지만 인덱스 $+1$ 이 개수가 되므로 그냥 사용하면 된다.

2. 투 포인터

투 포인터의 경우 $A$ 와 $B$ 각각 정렬 후 앞 쪽에 포인터를 하나씩 배치했다. 이후 $A$ 의 포인터에 해당하는 원소가 $B$ 의 포인터에 해당하는 원소보다 크면 $B$ 의 포인터를 오른쪽으로 한 칸 이동하고 작거나 같아지면 $B$ 의 포인터에 해당하는 수를 카운팅했다. 역시 인덱스가 개수보다 1개 작아서 바로 사용하면 된다.

---

2. 코드

1. 이분 탐색 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int[] A = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                A[i] = Integer.parseInt(st.nextToken());
            }

            int[] B = new int[M];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                B[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(B);

            int cnt = 0;
            for (int n : A) {
                cnt += lowerBound(B, n);
            }

            sb.append(cnt).append("\n");
        }

        System.out.println(sb);
    }

    static int lowerBound(int[] arr, int key) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = (left + right) / 2;

            if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 투 포인터 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int[] A = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                A[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(A);

            int[] B = new int[M];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                B[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(B);

            int pivotA = 0;  // A의 포인터
            int pivotB = 0;  // B의 포인터
            int cnt = 0;

            while (pivotA < N) {
                if (pivotB < M && A[pivotA] > B[pivotB]) {
                    pivotB++;
                } else {
                    cnt += pivotB;
                    pivotA++;
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.println(sb);
    }
}

3. 이분 탐색 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        for (int& x : a) cin >> x;

        vector<int> b(m);
        for (int& x : b) cin >> x;
        sort(b.begin(), b.end());

        int cnt = 0;
        for (int x : a) {
            cnt += lower_bound(b.begin(), b.end(), x) - b.begin();
        }

        cout << cnt << '\n';
    }
}

4. 투 포인터 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        for (int& x : a) cin >> x;
        sort(a.begin(), a.end());

        vector<int> b(m);
        for (int& x : b) cin >> x;
        sort(b.begin(), b.end());

        int pa = 0;  // A의 포인터
        int pb = 0;  // B의 포인터
        int cnt = 0;

        while (pa < n) {
            if (pb < m && a[pa] > b[pb]) {
                pb++;
            } else {
                cnt += pb;
                pa++;
            }
        }

        cout << cnt << '\n';
    }
}

---

3. 풀이 정보

1. 이분 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	392 ms	33932 KB	1515 B

2. 투 포인터 [Java]

언어	시간	메모리	코드 길이
Java 11	428 ms	34932 KB	1450 B

3. 이분 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	24 ms	2296 KB	542 B

4. 투 포인터 [C++]

언어	시간	메모리	코드 길이
C++ 17	24 ms	2296 KB	736 B

---