문제 개요
소문자로만 구성된 문자열 리스트 words가 주어지며, 모든 단어의 길이는 서로 같다고 가정합니다. 이때 우리가 확인해야 할 것은 이 단어들 중에서 딱 한 글자만 다른 두 문자열이 존재하는지 여부입니다.
예를 들어 입력이 words = ["seed", "pick", "lick", "root", "live"]라면 결과는 True가 됩니다. "pick"과 "lick"은 첫 번째 글자만 다를 뿐 나머지 세 글자는 완전히 동일하기 때문입니다.
해결 접근 방법
이 문제는 와일드카드(*)를 활용한 패턴 매칭으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 단어에서 한 글자씩 *로 치환한 패턴을 만들어, 이미 등장했던 패턴과 비교하는 것입니다. 서로 다른 두 단어가 동일한 패턴을 공유한다면, 그 두 단어는 정확히 한 글자만 다르다는 의미가 됩니다.
- 빈 집합(set) s를 하나 생성합니다.
- 리스트의 각 단어 word에 대해 다음 과정을 반복합니다.
- 단어의 각 위치 i에 대해 word[:i] + "*" + word[i+1:] 형태의 패턴을 만듭니다.
- 이 패턴이 이미 s에 존재한다면 True를 즉시 반환합니다.
- 존재하지 않는다면 해당 패턴을 s에 추가합니다.
- 모든 단어를 검사한 후에도 중복된 패턴이 없다면 False를 반환합니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해해 보겠습니다.
def solve(words):
s = set()
for word in words:
for i, w in enumerate(word):
if word[:i] + "*" + word[i + 1 :] in s:
return True
else:
s.add(word[:i] + "*" + word[i + 1 :])
return False
words = ["seed", "pick", "lick", "root", "live"]
print(solve(words))입력
["seed", "pick", "lick", "root", "live"]
출력
True
시간 및 공간 복잡도
단어의 개수를 N, 단어의 길이를 L이라고 하면, 각 단어마다 L개의 패턴을 생성하고 집합의 조회와 삽입에 각각 O(L)의 시간이 소요됩니다. 따라서 전체 시간 복잡도는 O(N × L²)입니다. 또한 저장되는 패턴은 최대 N × L개이고 각 패턴의 길이가 L이므로, 공간 복잡도 역시 O(N × L²)입니다.