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

문제

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

 

예제 출력 1

3 0 0 1 2 0 0 2

 

 

풀이

이분탐색으로 하면 된다는데.... 음 전혀 모르겠고요??? 보아하니 검색해야 하는 숫자의 개수(M)가 최대 50만이라서 이분탐색으로 해도 시간초과 나는 경우가 많은 것 같다. 이분탐색을 할 때 범위를 줄여주는 과정을 해야 한다는데 죄다 다른 언어만 있어서 일단 이분탐색이 아닌 다른 풀이를 생각해봤다.

 

C#에서의 풀이는 크게 2가지가 존재하는 것 같다.

1. Dictionary를 활용한 풀이

2. int Array를 활용한 풀이

 

 

Dictionary를 활용한 풀이

숫자를 key로, 배열 내 숫자의 개수를 value로 가지는 Dictionary를 만들고, 처음 받은 배열을 순회하면서 해당 숫자를 Key로 검색했을 때 나오는 value가 있는지 판단한다. 있으면 원래 value 값에 1씩 더해주고, 없으면 현재 숫자를 Key로 만들고 value에 1을 넣어준다.

이후 검색해야 하는 숫자인 두번째 배열을 순회하면서 dictionary.TryGetValue를 사용해 검색한 결과가 나오면 그대로 value를 출력하고, 없으면 0을 출력한다.

using System;
using System.Collections.Generic;
using System.Text;
namespace Baekjoon
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] card = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int m = int.Parse(Console.ReadLine());
            int[] numToCheck = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

            Dictionary<int, int> dict = new Dictionary<int, int>();
            StringBuilder sb = new StringBuilder();
            // push into dictionary
            for(int i = 0; i<n; i++)
            {
                dict[card[i]] = dict.TryGetValue(card[i], out int value) ? value + 1 : 1;
            }

            // search
            for (int i = 0; i < m; i++)
            {
                int res = dict.TryGetValue(numToCheck[i], out int value) ? value : 0;
                sb.Append(res.ToString() + " ");
            }
            Console.Write(sb);
        }
    }
}

 

 

Array를 이용한 풀이

문제에 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다는 조건이 있으므로 이를 활용한 방법이다. 20,000,001의 크기를 가진 int 배열을 선언하고, 각 숫자의 개수를 배열[10,000,000+숫자]에 저장하는 방식이다. 배열을 이렇게 만들면 각 숫자를 가지고 배열을 검색해 원 배열에 해당 숫자가 몇 개 들어있었는지 바로바로 알 수 있다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Baekjoon
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] card = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int m = int.Parse(Console.ReadLine());
            int[] numToCheck = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            
            int[] save = new int[20000001];
            for(int i = 0; i<n; i++)
            {
                save[10000000 + card[i]] += 1;
            }

            for(int i = 0; i<m; i++)
            {
                Console.Write(save[10000000 + numToCheck[i]] + " ");
            }


        }
    }
}