아나그램이란?
두 문자열 s0과 s1이 주어졌을 때, 이들이 서로 아나그램(anagram) 관계인지 판별하는 문제를 살펴보겠습니다. 아나그램이란 한 문자열의 글자 순서를 재배열하여 다른 문자열을 만들 수 있는 경우를 말합니다. 즉, 두 문자열이 같은 문자들을 정확히 같은 개수만큼 포함하고 있으면 아나그램입니다.
예를 들어, 입력이 s0 = "listen", s1 = "silent"라면, 두 단어는 같은 알파벳들로 구성되어 있으므로 출력은 True가 됩니다.
해결 접근 방법
이 문제는 매우 간단한 방법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- s0과 s1의 각 문자들을 정렬합니다.
- 정렬된 결과가 서로 동일하다면 True를 반환합니다.
- 그렇지 않다면 False를 반환합니다.
문자들을 정렬했을 때 결과가 같다는 것은 두 문자열이 동일한 문자 집합을 동일한 빈도로 가진다는 의미이므로, 이 방법만으로 아나그램 여부를 확실하게 판별할 수 있습니다.
구현 예제
다음 코드를 통해 실제 구현 방법을 살펴보겠습니다.
class Solution:
def solve(self, s0, s1):
return sorted(s0) == sorted(s1)
ob = Solution()
print(ob.solve("listen", "silent"))
입력
"listen", "silent"
출력
True
코드 설명
위 코드에서 sorted() 함수는 문자열을 인자로 받으면 각 문자를 사전순으로 정렬한 리스트를 반환합니다. 따라서 "listen"은 ['e', 'i', 'l', 'n', 's', 't']로, "silent" 역시 ['e', 'i', 'l', 'n', 's', 't']로 정렬되어 두 리스트가 일치하게 됩니다. 파이썬에서 리스트끼리 == 연산자로 비교하면 요소와 순서까지 모두 비교하므로, 이 비교 결과가 곧 아나그램 여부가 됩니다.
시간 복잡도
정렬에 걸리는 시간은 O(n log n)이며, 여기서 n은 문자열의 길이입니다. 따라서 전체 시간 복잡도는 O(n log n)입니다. 만약 더 효율적인 방법이 필요하다면, 각 문자의 등장 횟수를 딕셔너리나 collections.Counter로 세어 비교하는 O(n) 방식도 고려할 수 있습니다.