파이썬 알고리즘 문제: Anagram

애너그램이란 언어유희의 한 종류인데 단어를 구성하는 문자의 순서를 바꿔 새로운 단어를 만드는 놀이라고 한다. 영화를 보다보면 마치 암호문처럼 숨겨진 메세지로 종종 등장하기도 한다.

 

알고리즘 문제로 종종 등장하는 유형인데, 애너그램이라는 말 자체를 처음 들어 보는 경우 살짝 당황할 수 있으니 미리 연습해 두면 좋다.

 

palindrome, isogram, heterogram, pangram 등 문자의 배열과 관련된 패턴을 정의하는 형식이 여러가지 있는데 이러한 패턴의 성질을 이용한 문제를 푸는 알고리즘들이 다양하게 있다.

 

다음은 애너그램의 한 예이다.

heart - earth, part - trap, race - care도 애너그램의 예이다.

 

이번에 풀어볼 문제는 leetcode의 group anagram이다.

leetcode.com/problems/group-anagrams/

 

여러 개의 문자열을 입력하면 그 중 동일한 애너그램끼리 묶어주는 문제이다.

위 문제에서 strs = ["eat","tea","tan","ate","nat","bat"]를 예문으로 제시하였는데, 이 경우엔 [["bat"],["nat","tan"],["ate","eat","tea"]]와 같이 묶어주면 된다.

"nat"와 "tan"은 동일한 애너그램이며, "ate", "eat", tea"가 동일한 애너그램이기 때문이다.

 

"nat"와 "tan"이 동일한 애너그램이라는 것은 어떻게 알 수 있을까?

 

이 문제를 해결하는 가장 간단한 방법은 정렬을 하는 것이다.

"nat"를 문자 순서대로 정렬하면 'a', 'n', 't'가 되고,

"tan"도 문자 순서대로 정렬하면 'a', 'n', 't'가 된다.

 

즉, 두 문자가 애너그램 관계인지 확인하는 코드는 다음과 같이 작성할 수 있다.

 

"ate", "eat", "tea" 역시 모두 정렬하면, 'a', 'e', 't'가 된다.

 

여기서 우리는 알파벳 순으로 정렬된 단어인 "ant"와 "aet"를 각 단어들로 만들어진 애너그램의 대표 값으로 사용할 수 있다.

 

파이썬에서는 이렇게 만들어진 스트링을 key로 하는 dictionary에 저장하는 방식으로 같은 애너그램끼리 묶을 수 있다. 참고로 파이썬에서는 immutable hashable value를 key로 사용할 수 있다. (참고: itholic.github.io/python-list-tuple/)

 

sorted(a)의 결과 값을 key로 만드는 방법은 여러가지가 있을 수 있는데 leetcode의 첫번째 예제에서는 tuple을 사용하여 immutable hashable object로 변환하였다.

ans[tuple(sorted(s))].append(s)

물론 다음과 같이 스트링으로 사용하는 것도 가능하다.

ans[''.join(sorted(a))].append(a)

ans라는 dictionary에 정렬한 단어를 key로 하는 key-value pair에 mapping하므로써 같은 애너그램의 단어끼리 묶을 수 있다.

 

위 내용을 코드로 정리하면 다음과 같다.

참고로 defaultdict(list)는 dictionary의 default 값을 list, 특히 append가 가능하도록 empty list로 초기화하는 것이다.

 

그런데, leetcode에 이 코드를 submit하면 fail 하게 된다. 위 코드의 time complexity는 O(NKlogK)인데, strs에 대한 for loop 내부에서 각 문자열마다 sorting을 하기 때문이다. (참고: yabmoons.tistory.com/250)

따라서 문자열을 sorting을 하지 않고 dictionary key를 생성하는 방법이 필요하다.

 

애너그램의 각 단어를 구성하는 문자 수를 튜플로 생성하여 이것을 key로 사용하는 방법이 있다.

"ate"를 예로 들면 (1, 0, 0, 0, 1, 0, 0, ...., 1, 0, 0, ...)이 되는데, 'a'가 한 개, 'e'가 한 개, 't'가 한 개로 구성되어 있는 애너그램이라는 의미이다. 만약 "bab"라는 단어가 있다고 하면, (1, 2, 0, 0, 0, ...., 0) tuple을 key로 사용하는 것이다.

이것을 코드로 구현하면 다음과 같다.

문자 위치를 index로 하고 단어 내에 등장하는 문자의 개수를 값으로 하는 array를 생성하여 이 값을 key로 사용한다. 이렇게 하면 time complexity를 O(NK)로 줄일 수 있게 된다.

 

이렇게 완성된 코드는 다음과 같다.

참고: 위 내용은 leetcode에 작성된 것을 바탕으로 정리한 것입니다.