아나그램(Anagram)이란 두 문자열이 동일한 문자들로 구성되어 있되, 순서만 다른 경우를 말합니다. 예를 들어 'listen'과 'silent'는 같은 알파벳으로 이루어져 있으므로 서로의 아나그램입니다.
두 개의 문자열 s와 t가 주어졌을 때, 이들이 서로의 아나그램인지 판별하는 방법을 알아보겠습니다. 예를 들어 s = "bite", t = "biet"가 입력으로 주어진다면, 두 문자열은 같은 문자들로 구성되어 있으므로 결과는 True가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 문자열 s와 t의 길이가 다르면 False를 반환합니다. 길이가 다르면 아나그램일 수 없기 때문입니다.
- s와 t의 각 문자들을 정렬합니다.
- 정렬 후 두 문자열이 완전히 같으면 True, 그렇지 않으면 False를 반환합니다.
예제 코드
def solve(s, t): if len(s) != len(t): return False s = sorted(s) t = sorted(t) return s == t s = "bite" t = "biet" print(solve(s, t))
입력
"bite", "biet"
출력
True
코드 설명
위 코드의 동작 원리를 살펴보겠습니다.
- 길이 비교: 먼저 len() 함수로 두 문자열의 길이를 비교합니다. 길이가 다르다면 즉시 False를 반환하여 불필요한 연산을 줄입니다.
- 정렬: Python 내장 함수 sorted()를 사용하면 문자열이 문자 단위로 정렬된 리스트로 변환됩니다. 예를 들어 sorted("bite")는 ['b', 'e', 'i', 't']를 반환합니다.
- 비교: 정렬된 두 리스트가 동일한지 비교합니다. 아나그램이라면 정렬했을 때 반드시 같은 결과가 나오므로 True가 반환됩니다.
시간 복잡도
이 방법의 시간 복잡도는 O(n log n)입니다. 여기서 n은 문자열의 길이이며, 정렬에 소요되는 시간이 지배적입니다.
참고로, 더 효율적인 대안으로 Counter를 사용하는 방법(O(n))도 있습니다.
from collections import Counter
def solve(s, t):
return Counter(s) == Counter(t)Counter는 각 문자의 등장 횟수를 딕셔너리 형태로 저장하므로, 두 문자열의 문자 빈도수가 같은지 한 번의 비교로 확인할 수 있습니다.