[C#] 백준 1269번 문제풀이

문제번호: 1269

문제명: 대칭 차집합 

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

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

오늘은 자료구조를 이용한 대칭 차집합 구하기 문제를 풀어보았습니다. 대칭 차집합을 구하기 위해 List를 사용해보았지만 시간복잡도가 O(N)이고 원소 개수가 최대 200000개인것을 고려하면 시간초과가 날 수 밖에 없었습니다. 따라서 원수 유무를 따질 수 있는 Contains를 사용할 때 시간복잡도가 O(1)인 Hashset을 사용하였습니다.
다음은 정답코드입니다.

 

public static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int[] anbn = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int an = anbn[0];
    int bn = anbn[1];

    int[] anArray = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int[] bnArray = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

    sw.WriteLine(CountInCluded(anArray, bnArray) + CountInCluded(bnArray, anArray));

    sr.Close();
    sw.Close();
}

public static int CountInCluded(int[] A, int[] B)
{
    var hashset = new HashSet<int>(A);
    int count = 0;
    foreach(int b in B)
    {
        if (!hashset.Contains(b))
            count++;
    }

    return count;
}