C++ 사전에서 특정 패턴과 일치하는 모든 문자열 찾는 방법

문제 소개

문자열 목록으로 구성된 사전(dictionary)과 하나의 패턴(pattern) 문자열이 주어졌을 때, 사전 안에서 패턴과 일치하는 모든 문자열을 찾아야 합니다.

예를 들어 사전이 ["abb", "xyz", "aab", "kmm"]이고 패턴이 "stt"라고 가정해 보겠습니다. 이때 결과는 "abb"와 "kmm"입니다. 패턴 "stt"는 서로 다른 한 글자 뒤에 같은 글자 두 개가 이어지는 구조이므로, 정확히 같은 구조를 지닌 문자열만 일치 대상이 됩니다.

해결 접근 방식

이 문제는 패턴을 특정 방식으로 인코딩하면 효율적으로 해결할 수 있습니다. 인코딩 후 패턴과 일치하는 사전의 단어는 패턴과 동일한 해시 값을 갖게 됩니다. 따라서 사전의 모든 단어를 순회하면서 인코딩 결과가 패턴의 해시와 같은 단어만 출력하면 됩니다.

인코딩 방법은 간단합니다. 각 문자가 처음 등장하는 순서대로 고유 번호를 부여하고, 문자열 전체를 번호의 나열로 변환합니다. 예를 들어 "stt"와 "abb"는 모두 "011"로 인코딩되므로 서로 일치하는 것으로 판단됩니다.

알고리즘 단계

1. 패턴 문자열을 인코딩하여 해시 값을 생성합니다.
2. 사전의 각 단어에 대해 길이가 패턴과 같은지 먼저 확인합니다.
3. 단어를 인코딩한 결과가 패턴의 해시와 동일하면 화면에 출력합니다.

C++ 예제 코드

#include<iostream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
 
// 문자열을 숫자 시퀀스로 인코딩하는 함수
string stringEncode(string str) {
    unordered_map<char, int> map;
    string encoded_str = "";
    int i = 0;
    for (char ch : str) {
        if (map.find(ch) == map.end())
            map[ch] = i++;
        encoded_str += to_string(map[ch]);
    }
    return encoded_str;
}
 
// 패턴과 일치하는 단어를 찾아 출력하는 함수
void matchedPattern(unordered_set<string> dict, string pattern) {
    int patt_len = pattern.length();
    string hash = stringEncode(pattern);
    for (string word : dict) {
        if (word.length() == patt_len && stringEncode(word) == hash)
            cout << word << " ";
    }
}
 
int main() {
    unordered_set<string> dict = {"abb", "xyz", "aab", "kmm"};
    string pattern = "stt";
    matchedPattern(dict, pattern);
}

실행 결과

kmm abb