[C#] 해시 기반 카운팅 알고리즘

문제

가장 많이 등장한 문자 찾기

문자열이 주어졌을 때, 가장 많이 등장한 알파벳 문자와 그 횟수 찾기. 대소문자는 상관하지 않는다.

 

• 예시 입력 : 'UnityDevelopment'
• 예시 출력 : 'n most used for Count : 3'

 

풀이

internal class Class1
{
	static void Main()
	{
		string input = "UnityDevelopment";

		Dictionary<char, int> calcCount = new();

		foreach (char x in input.ToLower())
		{
			if (calcCount.ContainsKey(x)) calcCount[x]++;
			else calcCount[x] = 1;
		}

		char maxChar = '\0';
		int maxCount = 0;

		foreach(var x in calcCount)
		{
			if(x.Value > maxCount)
			{
				maxChar = x.Key;
				maxCount = x.Value;
			}
		}


		Console.WriteLine($"{maxChar} most used for Count : {maxCount}");
	}
}

 

설명

주어진 문자열 'string input = "UnityDevelopment"' 을 문자 하나하나 분리하고, 그 문자마다의 사용 횟수를 동시에 저장하기 위해 Dictionary<char, int> 형태의 자료구조 사용.

 

foreach 반복문을 통해 input의 문자열 하나씩 검사 및 대소문자를 구별하지 않기 위해 ToLower() 메서드 사용.

반복문 내부에서는 ContainsKey() 를 통해 Dictionary 안에 현재 반복하는 문자가 포함되어 있는지 확인하고, 이를 if/else 로 처리하여 존재할 경우 횟수 1 추가, 없을 경우 1로 초기화.

 

횟수 카운트 반복문 이후 foreach 문을 다시 사용하여 제일 많은 횟수로 사용된 문자열 탐색.

 

 

foreach 문의 반복 과정은 배열의 길이만큼 진행하는 O(n),

Dictionary은 해시 기반 자료구조로 탐색/생성 과정이 O(1) 으로 진행되어

코드 전체의 평균 시간 복잡도는 O(n) 만큼 진행되는 효율적인 알고리즘이라 볼 수 있다.