C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

배열요소가 중복되는지를 체크하기 위해서 순차적으로 각 문자마다 나머지 배열요소를 비교하는 방법을 생각해 볼 수 있다. 하지만 이 방식은 O(N^2) Time Complexity를 갖는 방식이고, 좀 더 효율적인 방식으로 순차적으로 각 문자마다 먼저 출현 횟수를 해쉬테이블에 저장한 후, 다음 루프에서 출현 횟수가 1인 첫 문자를 리턴하는 방법을 고려할 수 있다. (문자가 ASCII 이고 해쉬테이블을 사용하지 않는 경우는 256개의 ASCII 문자 테이블에 출현 횟수를 저장할 수 있다)

void RunTest()
{
    string s = "abcabdefe";
    char ch = GetFirstChar(s.ToCharArray());
    Console.WriteLine(ch);
}

char GetFirstChar(char[] S)
{
    Dictionary<char, int> ht = new Dictionary<char, int>();

    foreach (char ch in S)
    {
        if (!ht.ContainsKey(ch))
            ht[ch] = 1;
        else
            ht[ch] += 1;
    }

    foreach (char ch in S)
    {
        if (ht[ch] == 1)
            return ch;
    }

    return '\0';
}