자료구조 - 애너그램 탐지 문제

연습문제 : 애너그램 탐지

애너그램(Anagram)은 한 문자열의 문자를 재배열해서 다른 뜻을 가지는 다른 단어로 바꾸는 것을 의미함. 두 개의 문자열이 주어졌을 때, 서로가 서로의 애너그램인지 아닌지의 여부를 탐지하는 함수를 만들어봐.

• elice 와 leice 는 애너그램. True를 리턴해야 함.
• cat 과 cap 는 애너그램이 아님. False를 리턴해야 함.
• iamlordvoldemort 와 tommarvoloriddle 은 애너그램. True를 리턴해야 함.
• 문자열의 모든 문자는 영어 소문자라고 가정.

def isAnagram(str1, str2):
    return None

def main():
    print(isAnagram('iamlordvoldemort', 'tommarvoloriddle')) # should return True
    print(isAnagram('cat', 'cap')) #should return False
    

if __name__ == "__main__":
    main()

 

>>>

배열을 활용한 해설

def isAnagram(str1, str2):
    str1List = list(str1)
    str2List = list(str2)
    str1List.sort()
    str2List.sort()

    # if (str1List == str2List) :  # 이렇게 풀어서 쓸 수도 있고
    #     return True
    # else:
    #         return False
    
    return (str1List == str2List)  # 이렇게 한 줄로 해도 True, False 결과가 나와

def main():
    print(isAnagram('iamlordvoldemort', 'tommarvoloriddle')) # should return True
    print(isAnagram('cat', 'cap')) #should return False
    

if __name__ == "__main__":
    main()

 

>>>

해쉬를 활용한 해설

def isAnagram(str1, str2):
    dic1 = {}    # 딕셔너리 만들어주고
    for ch in str1:    # str1을 돌면서 
        dic1[ch] = dic1.get(ch, 0) + 1    # 알파벳 하나하나를 키로 넣어서 딕셔너리에 그 키에 해당하는 빈도수를 계속해서 하나씩 증가시켜줘
    for ch in str2:
        if ch in dic1:
            if dic1[ch] == 0:
                return False
            else:
                dic1[ch] -= 1
                
        else:
            return False
    return True