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

문제번호: 14425

문제명: 문자열 집합

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

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

 

오늘은 문자열 집합 문제를 풀어보았습니다. 말 그대로 특정 문자열이 집합문자열 안에 포함되어 있는지 검사하면 되는 간단한 문제입니다. 저는 문제를 처음 풀 때 시간초과가 날 것을 예상했지만 List로 자료구조를 설계하여 코드를 제출하였더니 당연하게도 시간초과라는 결과가 도출되었습니다. 그래서 '값의 위치를 바로 계산해서 포함여부를 O(1)의 시간복잡도로 알아낼 수 있는 HashSet 자료구조를 이용하여 제출하였더니 빠른 속도로 정답을 맞힐 수 있었습니다.

 

그렇다면, HashSet은 어떻게 다른 자료구조와 다르게 모든 값들을 순회하며 찾는것이 아닌 값의 위치를 바로 계산해서 포함여부를 알아낼 수 있었던 것일까요?

 

HashSet의 해시함수는 다음과 같은 역할을 수행합니다.

int hash = value.GetHashCode();
int index = hash % bucketCount;

입력값이 균등하게 분산된 숫자로, 충돌 확률이 매우 낮게 설계되었습니다. 따라서 거의 항상 한 칸에 하나의 값만이 위치하게 됩니다. 즉, 항상 시간복잡도가 O(1)은 아니지만 거의 항상 그렇다는 것입니다.

 

다음은 정답코드입니다.

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

    int[] NM = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int N = NM[0];
    int M = NM[1];

    HashSet<string> list = new HashSet<string>();
    int count = 0;

    for (int i = 0; i < N; i++)
    {
        list.Add(sr.ReadLine());
    }
    for (int i = 0; i < M; i++)
    {
        string input = sr.ReadLine();
        if (list.Contains(input))
        {
            count++;
        }
    }

    sw.WriteLine(count);

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