문제
JavaScript로 다음 두 가지 연산을 지원하는 데이터 구조를 설계해야 합니다.
- addWord – 데이터 구조에 새로운 단어를 추가합니다. 배열(Array)처럼 이미 존재하는 자료구조를 활용해 데이터를 저장할 수 있습니다.
- search – 일반 문자열 또는 정규 표현식 형태의 패턴을 검색합니다. 패턴은 소문자 'a-z' 또는 '.'으로만 구성되며, '.'은 임의의 한 글자를 대체할 수 있는 와일드카드 역할을 합니다.
예를 들어 다음과 같이 동작해야 합니다.
addWord("sir")
addWord("car")
addWord("mad")
search("hell") === false
search(".ad") === true
search("s..") === true'hell'이라는 단어는 저장되어 있지 않으므로 false를 반환하고, '.ad'는 'mad'와, 's..'는 'sir'와 각각 패턴이 일치하므로 true를 반환합니다.
예제 코드
다음은 클래스와 프로토타입을 활용해 두 메서드를 구현한 전체 코드입니다.
class MyData{
constructor(){
this.arr = [];
};
};
MyData.prototype.addWord = function (word) {
this.arr.push(word)
};
MyData.prototype.search = function (word) {
let reg = new RegExp('^'+word+'$');
return !!this.arr.find(el => reg.test(el));
};
const data = new MyData();
data.addWord('sir');
data.addWord('car');
data.addWord('mad');
console.log(data.search('hell'));
console.log(data.search('.ad'));
console.log(data.search('s..'));실행 결과
콘솔 출력 결과는 다음과 같습니다.
false true true
코드 설명
1. 데이터 저장 구조
MyData 클래스의 생성자에서 배열 arr를 생성해 단어들을 순서대로 저장합니다. addWord 메서드는 push()를 사용해 배열의 맨 뒤에 새 단어를 추가하므로, 삽입 연산의 시간 복잡도는 O(1)입니다.
2. 정규 표현식을 이용한 검색
search 메서드는 전달받은 패턴 문자열 앞뒤에 ^와 $를 붙여 완전 일치(full match) 정규식을 동적으로 생성합니다. 예를 들어 '.ad'가 입력되면 /^.ad$/라는 정규식이 만들어지며, 여기서 '.'은 정규 표현식의 메타 문자로 임의의 한 글자를 의미하므로 별도의 처리 없이도 와일드카드 기능을 수행합니다.
3. 불리언 값 변환
Array.prototype.find는 조건에 맞는 요소가 없으면 undefined를 반환합니다. 따라서 이중 부정 연산자(!!)를 사용해 결과를 명확한 true/false 불리언 값으로 변환하여 반환합니다.
참고: 성능 개선 방향
위 구현은 단순하고 직관적이지만, 저장된 단어 수가 많아질수록 search는 모든 단어를 순회해야 하므로 시간 복잡도가 O(n)까지 증가할 수 있습니다. 대량의 단어를 빈번하게 검색해야 하는 상황이라면 트라이(Trie) 자료구조를 도입하는 것이 좋습니다. 트라이는 공통 접두사를 공유하는 노드 구조로 단어를 저장하며, '.' 와일드카드를 만나면 해당 위치의 모든 자식 노드를 재귀적으로 탐색하는 방식으로 효율적인 패턴 검색을 지원합니다.