문 제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입 력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

5
4 1 5 2 3
5
1 3 7 9 5

출 력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

1
1
0
0
1

코 드

결국 ‘시간 초과’.. 어떻게 풀어야할지 몰라서 알아본 결과 ‘Hashset’을 이용하여 빠른 검색하는 방식으로 해결! ‘Array.Exist’ (List.Contains)의 시간 복잡도는 O(n)이다!

using System;
using static System.Console;
using System.IO;
using System.Linq;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamWriter writer = new StreamWriter(OpenStandardOutput());
            StreamReader reader = new StreamReader(OpenStandardInput());

            int N = int.Parse(reader.ReadLine());
            int[] A = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();


            int M = int.Parse(reader.ReadLine());
            int[] B = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();

            foreach (int num in B)
            {
                if (Array.Exists(A, i => i.Equals(num)))
                    writer.WriteLine("1");
                else
                    writer.WriteLine("0");
            }

            writer.Close();
            reader.Close();
        }
    }
}

비교코드 - 1

아래 코드는 HashSet을 이용한 데이터 검색 방식이다! 위에서도 설명했지만 ‘Array.Exists’ (List.Contains)의 시간복잡도는 O(n)인 반면에, **‘HashSet'**과 **'Dictionary<int, bool>'**에서 데이터 조회 시간복잡도는 O(1)이다! 즉, 대량의 데이터를 검색하고 포함하는지 체크 여부는 후자가 효율적!

using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(ReadLine());

            HashSet<int> nums = new HashSet<int>();
            var A = ReadLine()!.Split().Select(int.Parse).ToArray();
            foreach (var num in A)
                nums.Add(num);

            int M = int.Parse(ReadLine());
            var B = ReadLine()!.Split().Select(int.Parse).ToArray();

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < M; i++)
            {
                if (nums.Contains(B[i]))
                    sb.AppendLine("1");
                else
                    sb.AppendLine("0");
            }

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

공 부