프로그래밍 면접 문제 16: Anagram Strings
프로그래밍 면접 문제 16: Anagram Strings
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 15: First Non Repeated Character in String
주어진 두 개의 문자열이 Anagram인지 확인합니다. 두 문자열이 공백, 구두점 및 대소문자를 무시한 상태에서 서로 동일한 문자를 사용하면 Anagram입니다. 두 문자열에서 모두 같은 수의 문자가 존재해야 합니다. 예를 들어, ‘Eleven plus two’ and ‘Twelve plus one’은 서로 의미있는 Anagram입니다.
먼저 두 문자열에서 공백과 구두점을 제외시키고 문자만 추출한 상태에서 소문자로 변환합니다. 그런 다음 두 문자열이 서로 Anagram인지 비교합니다. 지금부터는 문자열이라고 언급되면, 이런 변환이 수행되고, 각 문자들이 원래 순서를 유지한채 소문자만 포함되어 있다고 가정하겠습니다.
두 문자열에 모든 문자가 동일한 수가 포함되어 있으면 해당 문자열들은 Anagram입니다. 이 확인 작업을 하는 가능한 접근 방법 중 하나는 두 문자열을 정렬한 다음 두 문자열이 서로 같은지 비교하는 방법입니다. 이 방법의 복잡도는 O(NlogN)이며, 여기에서 N은 문자열에 포함된 문자의 수를 나타냅니다. 코드는 다음과 같습니다.
def isAnagram1(str1, str2):
return sorted(getLetters(str1))==sorted(getLetters(str2))
def getLetters(text):
return [char.lower() for char in text if char in string.letters]
정렬 방식을 사용하는 접근방식은 훌륭하지만 최적의 방법은 아닙니다. 선형 시간 복잡도를 갖는 솔루션이 더 좋습니다. 문제 해결과정에서 수를 세는 작업이 포함되기 때문에 해시테이블이 적합한 자료 구조입니다. 첫 번째 문자열에 포함된 각 문자의 횟수를 해시테이블에 저장합니다. 그런 다음 왼쪽에서 오른쪽 방향으로 두 번째 문자열을 확인하면서 첫 번째 문자열에서 기록한 각 문자의 횟수를 감소시킵니다. 문자의 횟수가 음수가 되거나 (두 번째 문자열이 더 많은 문자를 갖는 경우) 두 번째 문자열에 포함된 문자가 해시테이블에 존재하지 않으면 (첫 번째 문자열에 해당 문자가 포함되지 않은 경우) 두 문자열은 서로 Anagram이 아닙니다. 마지막으로 해시테이블에 기록한 문자 횟수가 모두 0인지 확인합니다. 그렇지 않은 경우에는 첫 번째 문자열에 더 많은 문자가 포함되어 있다는 의미가 됩니다. 또는 이를 비교하기 전에 두 문자열의 길이를 확인해서 횟수를 확인하는 절차를 피할 수 있습니다. 이렇게하면 두 문자열의 길이가 다르면 Anagram이 될 수 없기 때문에 프로그램을 초기에 종료시킬 수 있습니다. 코드는 다음과 같습니다.
def isAnagram2(str1, str2):
str1, str2 = getLetters(str1), getLetters(str2)
if len(str1)!=len(str2):
return False
counts=collections.defaultdict(int)
for letter in str1:
counts[letter]+=1
for letter in str2:
counts[letter]-=1
if counts[letter]<0:
return False
return True
코드에서는 파이썬의 defaultdict 해시테이블을 사용했습니다. 이 해시테이블은 딕셔너리(dictionary)에 특정 문자가 존재하지 않으면 값 0을 생성합니다. 이 솔루션은 최적이며 복잡도는 O(N) 입니다. 횟수를 저장하는데 해시테이블을 다시 한번 사용하면서 그 장점을 입증했습니다.
