[백준] 10816 숫자 카드 2 [C#]

첫째 줄에는 입력될 정수들의 개수가, 둘째 줄에는 정수들이 문자열 형식으로 한 줄로 입력된다.

셋째 줄에는 찾을 정수들의 개수가, 넷째 줄에는 찾을 정수들이 한 줄로 입력된다.

넷째 줄에 입력된 정수의 개수를 한 줄로 출력하면 되는 문제이다.

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
 
            int N = int.Parse(reader.ReadLine());
 
            int[] num = new int[20_000_001];
 
            string[] str1 = reader.ReadLine().Split();
 
            for (int i = 0; i < N; i++)
            {
                num[int.Parse(str1[i])+10_000_000]++;
            }
 
            int M = int.Parse(reader.ReadLine());
 
            string[] str2 = reader.ReadLine().Split();
 
            for (int a = 0; a < M; a++)
            {
                int low = -10_000_000; int high = num.Length - 1;
                bool found = false;
                while(high >= low && !found)
                {
                    int mid = (low + high) / 2;
                    if (mid == int.Parse(str2[a]))
                    {
                        found = true;
                        sb.Append(num[mid+10_000_000] + " ");
                        break;
                    }
                    else if (mid > int.Parse(str2[a]))
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
                if (!found)
                    sb.Append("0 ");
            }
 
            print.WriteLine(sb);
        }
    }
}

지금까지 항상 양수로 주어졌던 정수가 이제는 음수로도 주어진다.

그렇기 때문에, 인덱스 번호의 값을 증가시킬 때, 해당 인덱스 번호에 10_000_000을 더해서 증가시켜야 한다.

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
 
            int N = int.Parse(reader.ReadLine());
 
            int[] num = new int[20_000_001];
 
            string[] str1 = reader.ReadLine().Split();
 
            for (int i = 0; i < N; i++)
            {
                num[int.Parse(str1[i])+10_000_000]++;
            }
 
            int M = int.Parse(reader.ReadLine());
 
            string[] str2 = reader.ReadLine().Split();
 
            for (int j = 0; j < M; j++)
            {
                sb.Append(num[int.Parse(str2[j]) + 100_00_000] + " ");
            }
 
            print.WriteLine(sb);
        }
    }
}

문제 유형에 이분탐색이 써있길래 이분탐색을 사용했는데 (시간복잡도: nlogn)

알고보니 인덱스 번호를 가지고 직접 접근하면 됐다... (시간복잡도: n)