[C#] 백준 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보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

 

[ 코드 ]

1. 내 코드

class Program
{
    static int CountPairs(int[] A, int[] B)
    {
        Array.Sort(A);
        Array.Sort(B);
        int count = 0;
        int aIndex = 0;

        foreach (var b in B)
        {
            while (aIndex < A.Length && A[aIndex] <= b)
            {
                aIndex++;
            }
            count += A.Length - aIndex;
        }
        return count;
    }

    static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine());
        for (int t = 0; t < T; t++)
        {
            string[] sizes = Console.ReadLine().Split();
            int N = int.Parse(sizes[0]);
            int M = int.Parse(sizes[1]);
            int[] A = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] B = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int result = CountPairs(A, B);
            Console.WriteLine(result);
        }
    }
}

 

2. 다른 사람 코드

namespace Baekjoon;

using System;
using System.Text;

public class Program
{
    private static void Main(string[] args)
    {
        using var sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        var t = ScanInt(sr);
        var aList = new List<int>();
        var bList = new List<int>();
        var sb = new StringBuilder();
        for (int i = 0; i < t; i++)
        {
            int a = ScanInt(sr), b = ScanInt(sr), start = 0, ret = 0;
            for (int j = 0; j < a; j++)
            {
                aList.Add(ScanInt(sr));
            }
            for (int j = 0; j < b; j++)
            {
                bList.Add(ScanInt(sr));
            }
            aList.Sort();
            bList.Sort();
            foreach (var aItem in aList)
            {
                ret += BinarySearch(aItem);
            }
            sb.Append(ret).Append('\n');
            aList.Clear();
            bList.Clear();
            int BinarySearch(int item)
            {
                int l = start, r = bList.Count;
                while (l < r)
                {
                    var mid = (l + r) / 2;
                    if (item > bList[mid])
                    {
                        l = mid + 1;
                    }
                    else r = mid;
                }
                return start = l;
            }
        }
        Console.Write(sb);

    }

    static int ScanInt(StreamReader sr)
    {
        int c, n = 0;
        while (!((c = sr.Read()) is ' ' or '\n' or -1))
        {
            if (c == '\r')
            {
                sr.Read();
                break;
            }
            n = 10 * n + c - '0';
        }
        return n;
    }
}

 

흠.. 이분탐색이 뭘까... 되게 어려우면서도 애매한 이런 알고리즘..

너무너무 어렵다....

힝

 

[ 실행화면 ]

 

 

 

 

---

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