길이가 모두 같은 여러 개의 문자열로 이루어진 배열이 주어졌다고 가정해 보겠습니다. 이때 주어진 문자열 중 임의의 두 문자열이 같은 위치에서 단 한 글자만 다른 경우가 존재하는지 확인해야 합니다. 그러한 차이가 존재하면 True를 반환하고, 존재하지 않으면 False를 반환하면 됩니다.
예를 들어 입력이 dict = ['pqrs', 'prqs', 'paqs']와 같다면 출력은 True가 됩니다. 세 문자열이 모두 인덱스 1(두 번째 자리)에서 서로 다르기 때문입니다. 따라서 어떤 두 문자열을 골라 비교하더라도 동일한 위치에서 차이가 발생합니다.
문제 해결 접근 방법
이 문제는 마스킹(masking) 기법을 활용하면 효율적으로 해결할 수 있습니다. 각 문자열에서 한 글자씩 '.'으로 대체한 마스크 문자열을 만들고, 이전에 등장한 마스크와 동일한 것이 있는지 집합(set)으로 확인하는 방식입니다. 동일한 마스크가 두 번 나타난다는 것은, 두 문자열이 해당 위치를 제외한 나머지 부분이 완전히 같다는 의미이므로 조건을 만족합니다.
seens := 새로운 빈 집합(set) 생성
dict에 있는 각 단어(word)에 대해 반복:
단어의 각 인덱스 i와 문자 c에 대해 반복:
masked_word := word[:i] + '.' + word[i+1:] (i번째 문자를 '.'으로 대체)
masked_word가 seens에 이미 존재하면 → True 반환
그렇지 않으면 → masked_word를 seens에 추가
모든 반복이 끝나면 False 반환
파이썬 예제 코드
아래 구현을 통해 더 잘 이해할 수 있습니다.
def solve(dict): seens = set() for word in dict: for i, c in enumerate(word): masked_word = word[:i] + '.' + word[i+1:] if masked_word in seens: return True else: seens.add(masked_word) return False print(solve(['pqrs', 'prqs', 'paqs']))
입력
['pqrs', 'prqs', 'paqs']
출력
True
시간 복잡도 분석
문자열의 개수를 n, 각 문자열의 길이를 m이라 하면, 각 문자열마다 m개의 마스크를 생성하고 각 마스크 생성에는 O(m)의 시간이 걸리므로 전체 시간 복잡도는 O(n × m²)입니다. 공간 복잡도 역시 저장되는 마스크의 수에 비례하여 O(n × m²)입니다. 이중 루프로 모든 문자열 쌍을 직접 비교하는 O(n² × m) 방식보다 문자열이 많은 경우 훨씬 효율적입니다.