10816 숫자카드 (C#) [Silver IV]

10816번: 숫자 카드 2

 

 

들어가며

이 문제는 숫자 카드를 몇개 가지고 있는지 찾는 문제입니다.

 

상근이가 가지고있는 숫자 카드의 최대 개수는 50만개,

체크 해야할 숫자 카드의 최대 개수가 50만개이기 때문에 2중 for문을 사용하면 시간 초과가 발생합니다.

---

 

가장 빠르게 풀 수 있는 방법은 Dictionary를 통해 상근이가 가지고 있는 숫자 카드의 개수를 저장하는 것입니다.

Dictionary<숫자 카드, 개수> cards = new Dictionary<int>();

cards[숫자 카드] += 1;

 

하지만, 해당 문제는 이진 탐색 문제이기에 이진 탐색 풀이 방법을 공유하겠습니다.

 

 

풀이 방법

이진 탐색을 통해 상근이가 가지고 있는 숫자를 찾기 위해서는 우선, 상근이의 카드를 정렬 해줘야합니다.

정렬된 카드들을 이진 탐색을 통해 위치를 찾습니다.

 

66을 찾는 과정, 하얀 부분은 탐색 범위

 

 

여기서 문제는 카드의 존재 유무가 아니라 카드의 개수를 찾는 것 입니다.

이진 탐색을 사용하여 수를 찾을 때, 수만 찾는 것이 아니라 수의 인덱스도 알 수가 있게 됩니다.

이때, 조건문을 다르게 하여 연속된 수의 시작 위치가 나오게도 할 수 있고, 마지막 위치가 나오게도 할 수 있습니다.

 

if (nums[mid] > target)
    end = mid -1;
else
    start = mid + 1;

이진탐색이 종료될 때, start의 위치가 찾으려는 수의 마지막 위치가 됨

 

if (nums[mid] < target)
    start = mid + 1;
else
    end = mid - 1;

이진탐색이 종료될 때, start의 위치가 찾으려는 수의 시작 위치가 됨

 

즉, 두번의 이진탐색을 통해 두개의 위치를 찾을 수 있게 되며

두 값을 빼주면 해당 수의 개수를 구할 수 있게됩니다.

 

 

정답 코드

[많은 출력이 필요한 상황에는 StringBuilder를 활용하지 않으면 시간초과가 발생할 수 있습니다]

class Program
{
	static StringBuilder sb = new StringBuilder();

    static void Main(string[] args)
    {
        List<int> nums = new List<int>();
        List<int> cards = new List<int>();

        int N = int.Parse(Console.ReadLine());
        string[] nums_str = Console.ReadLine().Split(' ');

        int M = int.Parse(Console.ReadLine());
        string[] nums_strM = Console.ReadLine().Split(' ');


        for (int i = 0; i < N; i++)
        nums.Add(int.Parse(nums_str[i]));

        for (int i = 0; i < M; i++)
        cards.Add(int.Parse(nums_strM[i]));

        nums.Sort();

        int[] answer = new int[cards.Count];
        for (int i = 0; i < cards.Count; i++ )
        {
            int target = cards[i];
            int start = 0;
            int end = nums.Count - 1;

            while (start <= end)
            {
                int mid = (start + end) / 2;

                if (nums[mid] > target)
                    end = mid -1;
                else
                    start = mid + 1;
            }
            int A = start;


            start = 0;
            end = nums.Count - 1;
            while (start <= end)
            {
                int mid = (start + end) / 2;
                if (nums[mid] < target)
                    start = mid + 1;
                else
                    end = mid - 1;
            }
            int B = start;

            answer[i] = A - B;
        }



        for (int i = 0; i < answer.Length -1 ; i++)
        sb.Append(answer[i] + " ");
        sb.Append(answer[answer.Length - 1]);

        Console.Write(sb.ToString()); 
    }
}