단어 목록과 하나의 패턴이 주어졌을 때, 그 패턴과 일치하는 단어들을 찾는 문제를 Python으로 해결하는 방법을 알아보겠습니다.
문제 정의
여기서 말하는 '일치(match)'란 다음 조건을 의미합니다. 글자 치환(permutation) p가 존재하여, 패턴 내의 모든 글자 x를 p(x)로 바꿨을 때 대상 단어가 된다면 그 단어는 패턴과 일치합니다. 즉, 글자 자체가 달라도 구조(반복 형태)가 동일하면 일치하는 것으로 간주합니다.
예시
입력이 ["abc","deq","mee","aqq","dkd","ccc"]이고 패턴이 "abb"라고 가정해 보겠습니다. 이때 출력은 ["mee", "aqq"]가 됩니다.
- "mee" → m, e, e 구조로 "abb"의 a, b, b 구조와 동일합니다.
- "aqq" → a, q, q 역시 같은 구조입니다.
- 반면 "ccc"는 세 글자가 모두 같으므로 a ≠ b인 패턴 "abb"와는 치환 관계가 성립하지 않습니다.
해결 전략
핵심 아이디어는 각 단어를 정규화된 숫자 패턴 문자열로 변환한 뒤, 이를 서로 비교하는 것입니다. 새로운 글자가 처음 등장하면 새 번호를 부여하고, 이미 등장한 글자라면 처음 등장했을 때의 번호를 재사용합니다.
convert() 메서드 설계
- counter := 1, s := 빈 문자열로 초기화합니다.
- s에 counter의 문자열 값을 추가합니다.
- i를 1부터 단어 길이 - 1까지 순회하며 다음을 수행합니다.
- j := i - 1로 설정합니다.
- j가 0 이상인 동안 word[j] == word[i]이면 반복을 중단하고, 아니면 j를 1씩 감소시킵니다.
- j > -1이면(앞서 같은 글자가 있었다면) s += s[j]로 기존 번호를 재사용하고, 그렇지 않으면 counter를 1 증가시킨 후 그 값을 문자열로 s에 추가합니다.
- 최종적으로 s를 반환합니다.
전체 풀이 흐름
- 빈 배열 words_num과 result를 준비합니다.
- words의 각 요소 i에 대해 convert(i)의 결과를 words_num에 삽입합니다.
- pattern 역시 convert(pattern)으로 변환합니다.
- 0부터 len(words) - 1까지 순회하면서 words_num[i] == pattern이면 words[i]를 result에 추가합니다.
- result를 반환합니다.
구현 예제
class Solution(object): def findAndReplacePattern(self, words, pattern): words_num = [] result = [] for i in words: words_num.append(self.convert(i)) pattern = self.convert(pattern) for i in range(len(words)): if words_num[i] == pattern: result.append(words[i]) return result def convert(self,word): counter = 1 s = "" s+=str(counter) for i in range(1,len(word)): j= i -1 while j>=0: if word[j] == word[i]: break j-=1 if j >-1: s+=s[j] else: counter+=1 s+=str(counter) return s ob = Solution() print(ob.findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc"],"abb"))
입력
["abc","deq","mee","aqq","dkd","ccc"] "abb"
출력
['mee', 'aqq']
정리
이 방식은 각 단어를 글자 종류에 따른 번호 시퀀스로 정규화하기 때문에, 실제 글자가 무엇이든 구조만 같으면 동일한 변환 결과를 얻게 됩니다. 예를 들어 "abb", "mee", "aqq"는 모두 "122"로 변환되므로 패턴과 일치함을 손쉽게 판별할 수 있습니다. 시간 복잡도는 단어 수를 N, 단어 길이를 L이라 할 때 O(N × L²)이며, 딕셔너리 기반 매핑을 사용하면 O(N × L)까지 최적화할 수 있습니다.