[백준] 1764번: 듣보잡 [C#]

첫째 줄에 두 배열의 입력 횟수가 한 줄로 주어진다. (N, M)

두번째 줄부터 N번째 줄 까지 듣지 못한 사람들이 입력된다.

N+1 번째 줄부터 M번째 줄 까지 보지 못한 사람들이 입력된다.

모든 입력은 소문자로 주어지고, 각 배열에는 중복 입력이 허용되지 않는다.

두 배열에 모두 속하는 사람을 찾아 "사전순"으로 출력해준다

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[] num = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
            int NS = num[0]; int NH = num[1];
 
            string[] neverSeen = new string[NS];
            string[] neverHeard = new string[NH];
 
            for (int i = 0; i < NS; i++)
            {
                neverSeen[i] = reader.ReadLine();
            }
 
            for (int j = 0; j < NH; j++)
            {
                neverHeard[j] = reader.ReadLine();
            } Array.Sort(neverHeard);
 
            HashSet<string> set1 = new HashSet<string>(neverSeen);
 
            int count = 0;
            foreach (string a in neverHeard)
            {
                if (set1.Contains(a))
                {
                    sb.Append(a + "\n");
                    count++;
                }
            }
 
            print.WriteLine($"{count}\n" + sb);
        }
    }
}

지금까지는 string배열에 입력을 받아서 쪼개놓기만 한 후,  int형 배열에 넣어주는 방법을 사용했는데,

이제는 입력을 받은 즉시 int형으로 형변환 해서 int형 배열에 저장할 수 있게 되었다.

그리고 두 배열의 내용물을 비교할 때

전수조사 (시간 복잡도 O(n^2)) 혹은 이진 탐색 (시간 복잡도 O(log n)) 을 사용했었는데, 시간 초과가 뜨는 걸 보고 더 좋은 방법이 없을까 싶어서 찾아봤는데, HashSet 을 이용한 방법이 있었다.

이 방식을 사용하면 해시셋에 데이터를 입력하는 시간 O(n)과 데이터를 찾는데 O(1)의 시간만이 걸리기 때문에 시간을 아주 많이 줄일 수 있게 되었다.