문제 설명
주어진 단어 목록과 검색할 단어가 있을 때, 이 검색할 단어가 단어 목록에 포함되어 있는지를 체크하는 문제입니다. 이 문제는
사전(dictionary) 자료구조를 활용하여 해결할 수 있습니다. 이는 C#에서 Dictionary 클래스를 사용하여 쉽게 구현할 수 있습니다.
알고리즘 문제
문제
주어진 단어 목록 words가 주어질 때, 다음과 같은 checkWords 메소드를 작성하세요.
checkWords 메소드는 문자열 목록과 문자열을 인자로 받아, 해당 문자열이 목록에 있으면 true를 리턴하고,
없으면 false를 리턴해야 합니다.
예시
입력: words = ["apple", "banana", "cherry"], searchWord = "banana"
출력: true
문제 풀이
이 문제를 해결하기 위한 가장 효율적인 방법 중 하나는 해시 테이블을 사용하는 것입니다. 해시 테이블을 사용하여 단어 목록을
미리 저장하고, 검색할 때 O(1) 시간 복잡도로 단어를 찾아낼 수 있습니다. C#의 Dictionary 클래스를 활용하면
이러한 구현이 가능하므로, 아래의 단계로 문제를 해결하겠습니다.
단계 1: 단어 목록을 Dictionary로 변환하기
먼저, 주어진 단어 목록을 Dictionary 형태로 변환합니다. 각 단어를 키(key)로 사용하고, 값(value)은
불필요하게 빈 문자열을 사용하겠습니다.
// C# 코드
using System;
using System.Collections.Generic;
public class DictionarySearch
{
private Dictionary wordDictionary;
public DictionarySearch(List words)
{
wordDictionary = new Dictionary();
foreach (var word in words)
{
wordDictionary[word] = true; // Value는 필요 없으므로 true로 설정
}
}
}
단계 2: 단어 검색 메소드 작성하기
이제 checkWords 메소드를 작성하겠습니다. 이 메소드는 사전에서 검색할 단어가 존재하는지 여부를 확인할 것입니다.
public bool CheckWords(string searchWord)
{
return wordDictionary.ContainsKey(searchWord);
}
단계 3: 최종 클래스 및 메소드 구현
위의 단계들을 결합하여 최종적인 솔루션 형태로 클래스를 완성하겠습니다.
using System;
using System.Collections.Generic;
public class DictionarySearch
{
private Dictionary wordDictionary;
public DictionarySearch(List words)
{
wordDictionary = new Dictionary();
foreach (var word in words)
{
wordDictionary[word] = true;
}
}
public bool CheckWords(string searchWord)
{
return wordDictionary.ContainsKey(searchWord);
}
}
class Program
{
static void Main(string[] args)
{
List words = new List { "apple", "banana", "cherry" };
DictionarySearch dictionarySearch = new DictionarySearch(words);
Console.WriteLine(dictionarySearch.CheckWords("banana")); // Output: true
Console.WriteLine(dictionarySearch.CheckWords("grape")); // Output: false
}
}
복잡도 분석
– 시간 복잡도: O(1) – 해시 테이블을 사용하여 단어를 저장하고 검색하는 것이 최적으로 O(1) 시간에 수행됩니다.
– 공간 복잡도: O(n) – 주어진 단어 목록의 크기 n에 비례합니다.
중요 포인트
– 문제를 해결하기 위해 Dictionary 클래스를 사용하는 것이 핵심입니다. 이는 빠른 검색 속도를 보장합니다.
– 문자열 비교의 경우, 대소문자 구별 여부에 따라 결과가 달라질 수 있으므로 주의해야 합니다.
– 전체적인 코드를 수행해 본 후, 다양한 테스트 케이스를 통해 검증이 필요합니다.
결론
본 강좌에서는 C#을 활용하여 사전 찾기 문제를 해결하는 방법을 설명했습니다. 해시 테이블을 사용한 자료구조적 접근이
문제가 주어진 조건을 효율적으로 만족시킬 수 있음을 보였습니다. 실제 코딩 테스트에서도 이와 같은 자료구조의 사용이 빈번하게
나타나므로, 미리 연습하는 것이 중요합니다.