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

[ 문제 ]

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

[ 코드 ]

1. 내 코드

using System.Text;

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();

int n = int.Parse(sr.ReadLine());
int[] nNum = sr.ReadLine().Split().Select(int.Parse).ToArray();
int m = int.Parse(sr.ReadLine());
int[] mNum = sr.ReadLine().Split().Select(int.Parse).ToArray();

Array.Sort(nNum);

foreach (int num in mNum)
{
    int count = CountOccurrences(nNum, num); // 이진 탐색으로 중복 횟수 세기
    sb.Append($"{count} ");
}

sw.Write(sb.ToString().Trim());
sw.Flush();
sw.Close();
sr.Close();

int CountOccurrences(int[] arr, int target)
{
    int left = 0, right = arr.Length - 1;
    int start = -1, end = -1;

    // 이진 탐색으로 시작 위치 찾기
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
        {
            start = mid;
            right = mid - 1;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    left = 0;
    right = arr.Length - 1;

    // 이진 탐색으로 끝 위치 찾기
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
        {
            end = mid;
            left = mid + 1;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    // 시작과 끝 위치로 중복 횟수 계산
    if (start != -1 && end != -1)
    {
        return end - start + 1;
    }
    else
    {
        return 0;
    }
}

 

이진탐색 좀 어렵다....

 

[ 실행화면 ]

case: 1

 

 

 

 

 

---

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

10816번: 숫자 카드 2